自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:56:26，当前版本为作者最后更新于2024-10-02 10:58:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

第一个问题比较简单，只需要用优先队列模拟，里面存下当前每个农夫面试的奶牛的结束面试的时间即可，最后输出 q.top()。

重点在第二问。好像很多题解没说清楚为什么不能用并查集，这里举出一个例子：

输入：

8 3
4 4 5 1 2 3 4 1

它对应的农夫每个时刻面试的奶牛编号是这样的：

1 2 3
1 2 3
1 2 3
1 2 3
4 5 3
6 5 7
6 8 7
6 . 7
. . 7

在第 $4$ 时刻结束后，$1,2$ 号农夫可以交换，因此 Bessie 可能被第 $1,2$ 号农夫面试。

在第 $5$ 时刻结束后，第 $1,3$ 号农夫可以交换（如果先前 $1,2$ 号农夫已经交换则此时 $2,3$ 号农夫可以交换），但是交不交换无所谓，因为 Bessie 已经不可能被这两个农夫中的任何一个面试了。

而如果使用并查集，在第 $5$ 时刻结束后，会将 $1,3$ 号农夫合并，而先前已经将 $1,2$ 号农夫合并。因此，如果使用并查集，最终的答案会认为 $3$ 号农夫也是有可能面试到 Bessie 的，然而实际上不行，只不过是 $1,3$ 号农夫最终面试的奶牛编号可能不同罢了。

那么正确的解法应该是什么呢？

拿优先队列跑过一遍后，我们可以在中途存下每个奶牛开始面试和结束面试的时间。这个值是确定的，即使面试这些奶牛的农夫可能不确定。首先拿 Bessie 开始面试的时间找到结束面试的时间为这个值的奶牛，这些奶牛是有可能在此时让 Bessie 排到后面的。继续拿这些奶牛的开始时间找结束时间相同的奶牛，最终直到找到了编号在 $1$ 到 $k$ 之间的奶牛，那么 Bessie 有可能排在这些奶牛的后面，而面试这些奶牛的农夫编号就是这些奶牛的编号，存下这些编号即可。

具体实现时，注意到拿第 $i$ 号奶牛的开始时间找结束时间相同的奶牛时，不可能找到编号比 $i$ 大的奶牛，所以可以之间从 $n$ 到 $1$ 倒着跑一遍，拿一个 set 维护当前需要找结束时间为多少的奶牛。遍历到一个奶牛时，如果这个奶牛的结束时间正好是我们要找的，那么就把它的开始时间放到 set 里面。如果 $i\le k$，那么就把一个记录最终答案的 bool 数组标记一下即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[300005],st[300005],ed[300005];
priority_queue<int,vector<int>,greater<int>>q;
set<int>s;
bool b[300005];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,k;cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=k;i++){
		ed[i]=a[i];
		q.push(ed[i]);
	}
	for(int i=k+1;i<=n;i++){
		int x=q.top();q.pop();
		st[i]=x;ed[i]=x+a[i];
		q.push(ed[i]);
	}
	cout<<q.top()<<endl;
	s.insert(q.top());
	for(int i=n;i>=1;i--){
		if(s.find(ed[i])!=s.end()){
			s.insert(st[i]);
			if(i<=k)b[i]=1;
		}
	}
	for(int i=1;i<=k;i++)cout<<b[i];
	return 0;
}