题解：P11457 [USACO24DEC] Job Completion G

· · 题解

非常好的一道反悔自动机练习题。

与这题十分类似：P4053 建筑抢修，感兴趣可以先去做一下。

第一眼观看时，可以看出，这道题应该与每项工作的紧急程度有关。因为显而易见的，如果一项工作完成后还可以完成其他的工作，但其它工作完成后就不能再完成这项工作了，我们应当先完成这项工作。

举个例子，假设我们现在已经耗费了 100000 的时间，工作 a 的截止开始时间为 114514，工作所需时间为 2，工作 b 的截止开始时间为 123456，工作所需时间为 20000，此时如果先完成 b，时间就变成 120000，此时无法再完成 a。但如果先完成 a，此时时间变为 100002，我们仍有充足的时间去完成 b。所以可以得出结论，我们一般应当先完成最紧急的任务。

然而“紧急”是如何定义的呢？我们可以先猜想，截止开始时间越早，这项工作就越紧急。然而很快可以给出反例。

假设我们现在已经耗费了 100000 的时间，工作 a 的截止开始时间为 114514，工作所需时间为 2，工作 b 的截止开始时间为 114513，工作所需时间为 20000，此时如果先完成 b，时间就变成 120000，此时无法再完成 a。但如果先完成 a，此时时间变为 100002，我们仍有充足的时间去完成 b。

上面这个例子仅仅是在开头的例子上将 b 的截止开始时间修改为了 114513，此时会发现，我们仍然是先完成 a 更划算，但此时 b 的截止开始时间显然比 a 更早，因此我们的猜想被推翻了。

然而再观察这个例子，我们可以发现它的截止结束时间就是他的截止开始时间加上它的所需完成时间，也就是说，在这个截止结束时间之前，你必须要完成这项工作，而不是开始你的工作。

我们继续猜想，会不会一项工作的紧急程度是由截止结束时间决定的呢？观看上面两个例子，会发现该结论在上述例子中均成立。那么我们再使用数学证明。

设两个工作截止开始时间为 s_i 与 s_j，完成所需时间为 t_i 与 t_j，当前已耗费的时间为 time，如果我们的最优选择方式为先完成工作 i 再完成工作 j，也就是说先完成工作 i 能完成工作 j，反之则不行，那么显然有两个不等式，分别是 time+t_i\le s_j 与 time+t_j>s_i。

将第一个式子两边各加上 t_j，第二个式子两边同加上 t_i，可以得到 time+t_i+t_j\le s_j+t_j 与 time+t_j+t_i>s_i+t_i，发现此时两个式子的左边相同，利用不等式的传递性可得 s_j+t_j>s_i+t_i，显然，我们可以将之理解为，如果先完成工作 i 能完成工作 j，反之不行，那么工作 i 的截止结束时间一定早于工作 j，也就是一般来说，我们应当先完成截止结束时间较早的工作。

所以，我们可以给每项工作按照截止结束时间升序排序，然后依次处理，确认是否完成这项工作。

然而，这个结论在面对一大堆工作时会出问题。我们的结论仅适用于先完成 i 时能完成 j，反之不行的情况。如果两个工作一定冲突，我们该选谁呢？很显然，我们应当选择消耗时间较少的而非截止结束时间较早的。

有时也许由于我们的贪心，在前面选择了一个截止结束时间较早但耗时大于当前工作的，并且此时时间不够我们完成这项工作了，那么这就是前面所说的两个工作一定冲突的情况了。我们应当舍弃前面那个耗时较大的而选择现在这个。但如果前面耗时反而更小，那么我们就不用管，就当无事发生。

这样一种思路我们当然可以用大根堆来维护。我们先处理最紧急的，并依次往越来越不紧急的顺序去处理，每次处理时先将这次工作的耗时放进大根堆，如果时间充足就先完成这项工作，否则我们弹出之前耗时最长的工作，也就是大根堆的堆顶，然后再来完成这项工作。当然，如果这项工作本身就是耗时最长的，由于前面我们已经将它放入大根堆中，所以会直接将它自己弹出。然后再修改当前工作时间。

这时也许有同学要问，如果这项工作的耗时会导致工作时间不够怎么办？这种情况我们其实完全不用担心。因为我们是按照紧急程度升序排序后再处理的。凡是放入大根堆的，都一定是我们已经完成的工作。已完成的工作显然在此次工作之前处理，也就是说它的截止结束时间较早，在截止结束时间较早，且它的耗时大于我们当前工作的耗时的情况下，显然如果这项工作能完成，那么放弃这项工作去完成当前工作也是没有问题的。

都讲到这里了，思路已经十分清晰，接下来代码也很好实现了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
int n,ans,t,m;
pair<int,int> a[N];
priority_queue<int> q;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m;
    while(m--){
        cin>>n;
        for(int i=1;i<=n;i++){cin>>a[i].first>>a[i].second;a[i].first+=a[i].second;}
        sort(a+1,a+n+1);//排序
        while(q.size()) q.pop();//清空
        t=0;ans=0;
        for(int i=1;i<=n;i++){
            q.push(a[i].second);//放入大根堆
            if(t+a[i].second<=a[i].first){//能完成就完成
                ans++;
                t+=a[i].second;
            }else{
                t+=(a[i].second-q.top());//不能完成就放弃耗时最长的
                q.pop();
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}