USACO24OPEN Bessie's Interview S 题解

题意简述：

有 \(n\) 个奶牛，\(k\) 个农夫，\(k\le n\)，每一个奶牛有一个面试时长 \(t_i\)，表示面试这个奶牛要多长时间。\(0\) 时刻时对于所有的 \(1\le i\le k\)，第 \(i\) 个农夫会面试第 \(i\) 个奶牛，之后的面试顺序满足以下条件：

1. 若在某时刻 \(t\)，存在某个农夫已经面试完当前的奶牛，那么他会立即按顺序面试下一个还没有面试到的奶牛。
2. 如果当前存在 \(x>1\) 个农夫，那么可以随意面试还没面试到的下 \(x\) 个奶牛。

现在奶牛 Bessie 排在第 \(n+1\) 位，请求出她能面试的最早时间，以及可能会面试她的农夫有哪些，如果一个农夫可能面试她则输出了\(1\)，不可能则输出 \(0\)。

Solution：

考虑实际上不同的时间至多有 \(2n\) 个。我们可以考虑使用 map 来储存这是第几个最新出现的数，接着对于时间 \(t\)，如果存在一个时间 \(t_0\) 是可以转移到 \(t\) 的，那么我们就由 \(t\) 向 \(t_0\) 连边，最后由 Bessie 最早可以面试的时间逐渐向下走，因为面试时间为正整数，该图实际上是个有向无环图，最后记录可以走到的初始时间，再将这些时间对应的农夫标记，输出即可。

至于第二个限制，可以发现我们这里并不需要考虑是如何选择的，任意的选择方案最后得出的图总是同一个图，图是同一个，那么最终对应的农夫也是同样的。

需要注意的是不能重复加边，会爆空间。

我这里是直接使用 set 存边。

Code：

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define ll long long
#define ull unsigned long long
#define m_p make_pair
#define m_t make_tuple
#define inf (0x7f7f7f7f)
#define N 300010
using namespace std;
using namespace __gnu_pbds;
ll ti[N];
int mpcnt = 1;
typedef pair<ll, int> pii;
std::priority_queue<pii, vector<pii>, greater<pii>> q;
vector<int> hs[N], avi, ans;
set<int> a[N << 1];
map<ll, int> mp;
bitset<N << 1> vis, vis1;
void checkins(ll x)
{
	if (!mp.count(x))
	{
		mp[x] = mpcnt;
		++mpcnt;
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll n, k, cnt, beginc, nt = 0, fl = 0, x;
	cin >> n >> k;
	for (ll i = 1; i <= n; i++)
		cin >> ti[i];
	for (ll i = 1; i <= k; i++)
	{
		q.push(m_p(ti[i], i));
		checkins(ti[i]);
		hs[mp[ti[i]]].push_back(i);
	}
	beginc = mpcnt;
	cnt = k + 1;
	while (!q.empty())
	{
		nt = q.top().first;
		if (cnt > n)
			fl = 1;
		while (!q.empty() && q.top().first == nt)
		{
			avi.push_back(q.top().second);
			q.pop();
		}
		x = mp[nt];
		for (ll i = 0; i < avi.size(); i++)
			if (cnt <= n)
			{
				q.push(m_p(nt + ti[cnt], avi[i]));
				checkins(nt + ti[cnt]);
				a[mp[nt + ti[cnt]]].insert(x);
				++cnt;
			}
			else
				fl = 1;
		if (fl)
			break;
		avi.clear();
	}
	queue<int> qq;
	qq.push(mp[nt]);
	while (!qq.empty())
	{
		x = qq.front();
		qq.pop();
		vis[x] = 1;
		if (x < beginc)
			for (auto px : hs[x])
				vis1[px] = 1;
		for (auto y : a[x])
			if (!vis[y])
				qq.push(y);
	}
	cout << nt << "\n";
	for (int i = 1; i <= k; i++)
		cout << vis1[i];
	return 0;
}

时间复杂度为 \(O(n\log_2n)\)，附带大常数。

本来还想写写考场思路的，想了想有点丢人，还是不写了。