二分答案水題。

（像我這么蒻的人都能十幾分鐘A掉）

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

?

開始時間一定在從0到min(t[i]-s[i])的一段區(qū)間上，因此我們可以愉快地二分答案。

在二分答案之前，我們貪心地把結(jié)束時間從小到大排一遍序，于是就可以二分了。

最后如果結(jié)果是負(fù)數(shù)，證明無解，不能完成任務(wù)。輸出-1。

Check函數(shù)里，模擬累加一下當(dāng)前的時間加上最靠近ddl任務(wù)所花的時間，看能不能完成，進(jìn)行判斷。

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

?

轉(zhuǎn)載于:https://www.cnblogs.com/nopartyfoucaodong/p/9330073.html

總結(jié)

以上是生活随笔為你收集整理的Luogu P2920 时间管理【二分答案】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。