使用了二分法,为什么才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;
}