冬令营的测试2

题目传送门

思路：这道题是个二分答案，最重要的是$check$ 函数，判断的是每个同学能不能放到一个区间里面，如果没放完区间就用完了，那就返回false；如果同学放完了，区间没用完，就返回true。

AC代码：

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll n, m;

struct qujian {
	ll st, end;
}a[100005];

bool cmp(qujian x, qujian y) {
	return x.st < y.st;
}

bool check(ll x) {
	ll start = a[1].st, wz = 1;
	for(ll i = 2; i <= n; i++) {
		while(start + x > a[wz].end && wz <= m) wz++;
		if(wz == m + 1) return false;
		if(start + x < a[wz].st) start = a[wz].st;
		else start += x;
	}
	return true;
}

int main() {
	cin >> n >> m;
	ll maxn = 0;
	for(ll i = 1; i <= m; i++) {
        cin >> a[i].st >> a[i].end;
		maxn = max(maxn, a[i].end - a[i].st);
    }
	sort(a + 1, a + m + 1, cmp);
	ll l = 0, r = maxn;
	while(l <= r) {
		ll mid = (l + r) / 2;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout << r << endl;
	return 0;
}

然后获得了91分的好成绩（我这么逝的）。

这是因为不需要是maxn，要把它改成1e9。

AC代码：

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll n, m;

struct qujian {
	ll st, end;
}a[100005];

bool cmp(qujian x, qujian y) {
	return x.st < y.st;
}

bool check(ll x) {
	ll start = a[1].st, wz = 1;
	for(ll i = 2; i <= n; i++) {
		while(start + x > a[wz].end && wz <= m) wz++;//下一个区间
		if(wz == m + 1) return false;//区间用完了
		if(start + x < a[wz].st) start = a[wz].st;
		else start += x;
	}
	return true;
}

int main() {
	cin >> n >> m;
	for(ll i = 1; i <= m; i++) cin >> a[i].st >> a[i].end;
	sort(a + 1, a + m + 1, cmp);
	ll l = 0, r = 1e9;
	while(l <= r) {//二分
		ll mid = (l + r) / 2;
		if(check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	cout << r << endl;
	return 0;
}

点个赞吧