[CF1943E2]MEX Game 2

下文中称 \(\text{Alice}\) 为 \(L\)，\(\text{Bob}\) 为 \(Q\)。

题意

有 \(n\) 个数，记作 \(a_1,a_2,\ldots, a_n\)，开始有一个空集 \(b\)。每次 \(L\) 从 \(a\) 中取出一个数 \(x\)，将 \(x\) 放入集合 \(b\)，并将其从 \(a\) 中删除。\(Q\) 从 \(a\) 中删除最多 \(k\) 个数。\(L\) 的得分即为 \(b\) 的 $ \operatorname{MEX} \(。\)L$ 希望得分尽可能大，\(Q\) 希望得分尽可能小，在两者的最优策略下求最大得分。

暴力

容易发现，答案 \(ans\ge x\)。这就相当于当数列简化为 \([0,x-1]\) 时，\(L\) 可以从所有数中取一次。进一步，我们只需要求出满足该条件的最大 \(x\)。

对于 \(L\) 来说，他每次都会取最小的 \(f_j (0\leq j\lt i)\)，且 \(i\) 未选。

对于 \(Q\) 来说，虽然看上去 \(f_i\) 顺序是固定的，但我们可以发现 \(Q\) 删数的顺序并不固定，只需要构建 \(f\) 的排列 \(g_0,g_1,\ldots,g_{x-2},g_{x-1}\)，且 \(g_i\leq g_j(i\leq j)\)。

这样，我们就能总结出来 \(Q\) 的策略就是使元素的出现频率尽量小，但是取数之后必须要满足 \(g\) 的要求。由此可以得出，\(Q\) 最多进行 \(m\) 次防守，直接暴力模拟，复杂度 \(O(m^3 logm)=O(m^2)\cdot O(m)\cdot O(logm)\)。

正解

主体思路相同，但是复杂度需要适当优化。

记 \(sum=\sum_{i=1}^n f_i\)，如果 \(f_i=\lfloor \frac{s+i-1}{n}\rfloor\)，则 \(f=\{a,a,\ldots,a,a+1,a+1,\ldots,a+1\}\)。显然，二元组 \(f(n,sum)\) 就可以用来描述完整的 \(f\)。

例如 \(Q\) 单次删除数的数量最多为 \(4\)，即 \(k=4\)，则：

\(1\degree\) 参与模拟 \(L\) 删除数组第一个元素

\([1,2,3,5,5]\rightarrow[2,3,3,3]\rightarrow[1,2,2]\)

\(2\degree\) 不参与模拟 \(L\) 删除数组第一个元素

\([1,2,3,5,5]\rightarrow[1,2,3,3,3]\rightarrow[1,1,2,2,2]\)

此时发现 \([1,2,2]\) 并不是 \([1,1,2,2,2]\) 的后缀。

故而说，假设我们不模拟 \(L\) 删除数组第一个元素，转而模拟 \(Q\)。可以发现，为了删掉 \(index\leq i\) 中的数，我们必须要使 \(f_{i+1}=f_{i+2}=\ldots=f_n\)。

如果在 \(e\) 轮操作后得到了形如 \(f\) 的数组，那必然 \(f(n-e,\sum_{i=e+1}^n f_i - e\cdot k)\)。为了找到正确的 \(e\)，我们可以直接二分查看数组的后缀的 \(\Delta\) 是否满足 \(\Delta\gt f_p\)，其中 \(\Delta\) 为过程中删去的总量。

由于 \(f(n,sum)\rightarrow f(n-1,s-k-\lfloor\frac{s}{n}\rfloor)\)，我们可以算每个 \(n\) 对应的最小 \(sum\)，使得 \(L\) 得到最大得分。

具体实现：双指针，复杂度：\(O(mlogm)\)

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 200010;
ll T, m, k;
ll id[N], f[N];
ll g[N], pre[N], h[N];

bool cmp(ll x, ll y) {return f[x] < f[y];}

bool check(ll x)
{
	ll cnt;
	cnt = 0;
	for (int i = 0; i <= m; i++)
	{
		if (id[i] <= x)
		{
			h[cnt] = f[id[i]];
			if (cnt > 0) pre[cnt] = pre[cnt - 1];
			pre[cnt] += h[cnt];
			cnt++;
		}
	}
	if (!h[0]) return true;
	ll j;
	j = 1;
	for (int i = 1; i <= x; i++)
	{
		while ((pre[i] - pre[j - 1] - j * k) / (i - j + 1) > h[j]) j++;
		if (pre[i] - pre[j - 1] - j * k <= g[i - j + 1]) return true;
	}
	return false;
}

int main()
{
	scanf("%lld", &T);
	while (T--)
	{
		scanf("%lld%lld", &m, &k);
		for (int i = 0; i <= m; i++) scanf("%lld", &f[i]);
		for (int i = 0; i <= m; i++) id[i] = i;
		sort(id, id + m + 1, cmp);
		for (int i = 2; i <= m + 1; i++)
		{
			ll x;
			x = g[i - 1] + k;
			g[i] = x + (x / (i - 1));
		}
		ll l, r, mid;
		l = 0, r = m + 1;
		while (l < r)
		{
			mid = (l + r) >> 1;
			if (check(mid)) r = mid;
			else l = mid + 1;
		}
		printf("%lld\n", l);
	}
	return 0;
}