P11457 [USACO24DEC] Job Completion G

Mr_Az · 2024-12-23 21:52:53 · 题解

P11457 [USACO24DEC] Job Completion G

Algorithm:

反悔贪心。

Solution:

如果不会的可以先去做 [JSOI2007] 建筑抢修。

考虑两个工作选择哪一个更优。设当前时刻为 t，当前有两个工作 i,j，且完成了 i 不能完成 j，而完成了 j 还可以完成 i。此时显然有先做 j 再做 i 更优。对应这种情况，变为表达式则有：

解得此时 s_i+t_i > s_j+t_j。

所以我们只需要先将所有的工作按照 s_i+t_i 从小到大进行排序，那么最终的操作顺序一定是这里的一段子序列。我们用反悔贪心去选择，记当前时间为 now：

1. 直接选择这个工作 now \le s，now=t+s;
2. 无法选择这个工作 now > s，如果之前完成的工作最长用时大于当前任务的 t，直接替换掉。

所有完成的工作只需要用大根堆存 t。

Code:

int T,n;    
pii a[N];
signed main(){
    read(T);
    while(T--){
        read(n);
        for(rint i=0;i<n;++i) read(a[i].first,a[i].second);
        sort(a,a+n,[](pii& a,pii& b){return (a.first+a.second)<(b.first+b.second);});
        priority_queue<int> q;
        int now=0,cnt=0;
        for(rint i=0;i<n;i++){
            auto [s,t]=a[i];
            if(now<=s){
                q.push(t);
                now+=t;
                cnt++;
            }//直接选择这工作
            else if(!q.empty()&&q.top()>t){
                now-=q.top();
                q.pop();
                q.push(t);
                now+=t;
            }//与之前的最长用时工作替换
        }
        cout<<cnt<<"\n";
    }
    return 0;
}