Luogu P2920 时间管理【二分答案】

二分答案水题。

（像我这么蒻的人都能十几分钟A掉）

https://www.luogu.org/problemnew/show/P2920

 

开始时间一定在从0到min(t[i]-s[i])的一段区间上，因此我们可以愉快地二分答案。

在二分答案之前，我们贪心地把结束时间从小到大排一遍序，于是就可以二分了。

最后如果结果是负数，证明无解，不能完成任务。输出-1。

Check函数里，模拟累加一下当前的时间加上最靠近ddl任务所花的时间，看能不能完成，进行判断。

code

#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f

using namespace std;
int n,ans;
int l,r=inf;
struct task{
    int t,s;
}a[2000];
bool cmp(task x,task y)
{
    return x.s<y.s;
}
bool check(int x)
{
    int now=x;
    for(int i=1;i<=n;i++)
    {
         if(now+a[i].t<=a[i].s) now+=a[i].t;
         else return false;
    }
    return true; 
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].t,&a[i].s);
        r=min(r,a[i].s-a[i].t);
    }
    sort(a+1,a+1+n,cmp);
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    ans=l ? l : -1;
    printf("%d",ans);
    return 0;
}