题解 P2920 【 时间管理Time Management】

本题其实思路很好想，也有很多实现方式。在这里详细介绍一下好写不容易挂的二分答案。 --- 关于二分： **最常见的**模板大概就长这样了 ```cpp //此处l、r需要根据题目要求定义. while(l <= r) { mid=(l+r)>>1; if(check(mid)) ans=mid, l=mid+1; else r=mid-1; } ``` 顾名思义，二分答案枚举的是答案，它的精髓就在于`check`函数了，二分答案又适用于哪些题目呢？ - 最大值最小、最小值最大 - 满足条件的第k个数 --- 那么二分答案怎么想，怎么写呢？以本题为例，要求最迟的工作时间x，我们就可以**枚举时间x判断这个时间能否完成任务**，然后不断往后推（因为求最迟的），因而`l=mid+1`，也就是说对于时间x，必须满足**可以完成工作**的条件 很容易想到对它们的截止时间排序，然后依次判断，如果这时的x满足于$x+a_i.t <= a_i.end$ 那么x加上这次完成所需的时间对下一个$a_i$再次判断，`check`函数的思路也就出来了： ```cpp inline bool check(int x) { for(register int i=0; i<n; ++i) { if(x+a[i].t <= a[i].end) x+=a[i].t; /* 如果可以满足要求就加上这次工作的时间 看x下一次是否能满足期限内下个任务要求 */ else return false; } return true; } ``` --- 那么结合刚刚所说的右逼答案此题就很快能写出来了 ```cpp # include <cstdio> # include <cstdlib> # include <iostream> # include <no-copy.h> # include <algorithm> using namespace std; inline void gi(int &x) { x=0;int t=1,k=getchar(); for(;k<'0'||k>'9';k=getchar())if(k=='-')t=-1; for(;k>='0'&&k<='9';k=getchar())x=(x<<1)+(x<<3)+(k^48);x*=t; } const int N=1000+5; int n; struct NODE { int t, end; //t是工作所需的时间，end是截止时间 bool operator < (const NODE &other) const { return end < other.end; } } a[N]; inline bool check(int x) { for(register int i=0; i<n; ++i) { if(x+a[i].t <= a[i].end) x+=a[i].t; else return false; } return true; } int main(void) { gi(n); for(int i=0; i<n; ++i) gi(a[i].t), gi(a[i].end); sort(a, a+n); //对截止时间排序，越早的自然越先做 int l=0, r=a[n-1].end+5, mid, ans=-1; /* r根据题目要求取一个不可取的值，这里取的是最晚的截止日期，因为显然不可能此时完成工作 如果无解输出-1，所以直接把ans设为-1，如果没有时间x满足要求就直接输出-1了 */ while(l <= r) { mid=(l+r)>>1; if(check(mid)) //每次枚举时间x看看是否能从第x分钟开始做完成任务 ans=mid, l=mid+1; else r=mid-1; } printf("%d", ans); return 0; } ``` 本题的`check`思路很简单，大家也可以做做[木材加工](https://www.luogu.org/problemnew/show/P2440)、[砍树](https://www.luogu.org/problemnew/show/P1873)练练手 如果有帮助的话请扣个赞QwQ，有问题欢迎在评论指出或提问