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

二分答案水题。

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

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

 

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

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

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

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

code

1 #include<cstdio> 2 #include<algorithm> 3 #define inf 0x3f3f3f3f 4 5 using namespace std; 6 int n,ans; 7 int l,r=inf; 8 struct task{ 9 int t,s; 10 }a[2000]; 11 bool cmp(task x,task y) 12 { 13 return x.s<y.s; 14 } 15 bool check(int x) 16 { 17 int now=x; 18 for(int i=1;i<=n;i++) 19 { 20 if(now+a[i].t<=a[i].s) now+=a[i].t; 21 else return false; 22 } 23 return true; 24 } 25 26 int main() 27 { 28 scanf("%d",&n); 29 for(int i=1;i<=n;i++) 30 { 31 scanf("%d%d",&a[i].t,&a[i].s); 32 r=min(r,a[i].s-a[i].t); 33 } 34 sort(a+1,a+1+n,cmp); 35 while(l<r) 36 { 37 int mid=(l+r+1)>>1; 38 if(check(mid)) l=mid; 39 else r=mid-1; 40 } 41 ans=l ? l : -1; 42 printf("%d",ans); 43 return 0; 44 } View Code

 

转载于:https://www.cnblogs.com/nopartyfoucaodong/p/9330073.html

总结

以上是生活随笔为你收集整理的Luogu P2920 时间管理【二分答案】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。