求助
查看原帖
求助
727723
ypyxc楼主2022/6/22 10:49

使用了二分法,为什么才70分啊有好几个案例没过

#include<iostream>
#include<bitset>
#include<algorithm>
using namespace std;
struct work
{
	int T, S;
};
work arr[1005];
int N;
bool cmp(work&a, work&b)
{

	if (a.S - a.T == b.S - b.T)return a.T < b.T;
	return a.S - a.T < b.S - b.T;
}
bool is_ok(int time)//time是开始的时间
{
	for (int cur = 1; cur <= N; cur++)//cur是现在要进行的任务
	{
		if (time <= arr[cur].S - arr[cur].T)
		{
			time = time + arr[cur].T;
		}
		else
			return false;
	}
	return true;
}
int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i].T >> arr[i].S;
	sort(arr + 1, arr + N + 1,cmp);


	int L = 0, R = 1000001;

	while (L + 1 < R)//最少两个还在里面
	{
		int mid = L + (R - L)/2;
		if (is_ok(mid))L = mid;
		else
			R = mid;
	}
	if (is_ok(L))cout << L;
	else
		cout << -1;
}
2022/6/22 10:49
加载中...