题解：P11457 [USACO24DEC] Job Completion G

xiaoliebao1115 · 2025-01-05 13:32:42 · 题解

感觉题解区很多都没有证明清楚，自己来一篇题解。

sol

假设有两个工作 i 先完成劣于 i+1 先完成，设 sum 表示 i 之前的工作已经花费的总时间。可能的情况只有 i 先完成会使得 i+1 无法完成，但反过来可以。

那么有 sum+t_i>s_{i+1}，但 sum+t_{i+1}\le s_i，有 s_{i+1}-t_i<sum\le s_i-t_{i+1}，整理得 s_{i+1}+t_{i+1}<s_i+t_i，所以显然可以对 s_i+t_i 排序，按照这样的顺序遍历进行反悔贪心。

• 如果 sum<=s_i 的话，sum 加上 t_i 即可。
• 否则，找到前面已经完成的 t_i 最短的工作记作 k，将他的时间与当前比较，如果当前 t 较小则将那个踢掉，当前加入，否则不变。

这样很对，但需要证明将那个踢掉之后一定能加入当前 i。假设 i 上一个做的工作是 j，那么显然有 sum-t_j\le s_j，我们需要证明的是 sum-t_k\le s_i，也就是 sum-t_j+(t_j-t_k)\le s_j+(-s_j+s_i)，括号外的部分已经成立，考虑括号中的增量，也就是需要证明 t_j-t_k\le -s_j+s_i，由于排序可知 s_j+t_j\le s_i+t_i<s_i+t_k，那么 t_j-t_k\le-s_j+s_i 成立，命题成立。

code

使用优先队列维护即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nn=3e5+5;
int t,n;
struct node{
    int s,t;
};
node x[nn];
inline bool cmp(node l1,node l2){
    return l1.s+l1.t<l2.s+l2.t;
}
priority_queue<int> q;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>x[i].s>>x[i].t;
        sort(x+1,x+n+1,cmp);
        int sum=0,ans=0;
        for(int i=1;i<=n;i++){
            if(sum<=x[i].s){
                sum+=x[i].t;
                q.push(x[i].t);
                ans++;
            }
            else{
                int tmax=q.top();
                if(tmax>x[i].t){
                    q.pop();
                    sum=sum-tmax+x[i].t;
                    q.push(x[i].t);
                }
            }
        }
        while(!q.empty()) q.pop();
        cout<<ans<<endl;
    }
    return 0;
}