记录编号	596198	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[USACO24 Open Silver]Bessie’s Interview	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	2.800 s
提交时间	2024-10-23 13:06:47	内存使用	6.33 MiB

/*
使用优先队列来模拟这个过程。
我们把多个农民同时完成的情况称为一个事件。
对于每个事件，存储完成的农民集合。
暂时以任意顺序将接下来的几头牛分配给这些农民。
由此，我们可以确定贝西（Bessie）面试的时间。
考虑如果我们按时间逆序遍历这些事件会发生什么。
如果农民 x 在某事件里，那么任何与他同时完成的农民都可能是贝西的面试官。
实际上，当我们逆着时间回溯时，每当贝西可能的面试官集合与一个事件中的农民集合相交时，
该事件中的任何农民都可能最终成为贝西的面试官。
*/
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using pli = pair<LL, int>;

#define cost first
#define id second

int main() {
	freopen("interview.in","r",stdin);
	freopen("interview.out","w",stdout);
	int n, k; 
	cin >> n >> k;
	
	vector<LL> t(n);
	for (int i = 0; i < n; i++) cin >> t[i];
	//小顶堆，先按first升序，first相等，按second升序
	priority_queue<pli, vector<pli>, greater<pli> > q;
	for (int i = 0; i < k; i++) q.push({t[i], i});
	//先入队k头牛让k名农夫面试
	int cur_cow = k;//当前待面试的奶牛编号
	pli last;
	vector<vector<int>> events;
	
	while (true) {
		vector<pli> ev;
		do {//将和队头农民一起结束当前面试的农民存入 ev
			ev.push_back(q.top());//
			q.pop();
		} while (!q.empty() && q.top().cost == ev[0].cost);
		
		if (ev.size() > 1) {//将同一事件的农民存入events
			vector<int> farmers;
			for (pli e : ev) farmers.push_back(e.id);
			events.push_back(farmers);//
		}
		
		if (cur_cow + ev.size() > n) {
			last = ev[0];//除贝西外最后一头面试的牛
			break;
		}
		
		for (pli e : ev) {//将后续待面试的牛逐个分给本批次农民
			q.push({e.cost + t[cur_cow], e.id});//当前面试花费的时间+待面试牛的花费时间
			cur_cow++;
		}
	}//end while
	
	cout << last.cost << "\n";
	
	vector<bool> can_interview(k, false);
	can_interview[last.id] = true;//上面求出的面试贝西的农民
	//按时间逆序遍历每个事件农民集合
	for (int i = (int)events.size() - 1; i >= 0; i--) {
		bool intersect = false;
		for (int j : events[i]) {
			if (can_interview[j]) {//本批有可能面试贝西的农民
				intersect = true;
				break;
			}
		}
		if (intersect) {//如果本批有可能面试贝西的农民，则本批均可能面试贝西
			for (int j : events[i]) {
				can_interview[j] = true;
			}
		}
	}
	vector<int> ans;
	for (int i = 0; i < k; i++) {
		cout << can_interview[i]<<(i==k-1?"\n":"");
	}
	return 0;
}