自动搬运

查看原文

来自洛谷，原作者为

	Mr_Az 我的尸体不会腐烂在泥土里，我会像鸟儿一样死在天空中。

搬运于2025-08-24 23:07:29，当前版本为作者最后更新于2024-12-23 21:52:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11457 [USACO24DEC] Job Completion G

Algorithm:

反悔贪心。

Solution:

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

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

1. $t+t_i>s_j$。
2. $t+t_j \le s_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;
}