XXI Open Cup Grand Prix of Korea H.Alchemy

数值为 $i (0 \le i < n)$ 的数有 $c_i$ 个. 从中选取一些数 $S, |S| > 0$, 变为 $\rm{mex}\{S\}$ 放回. 最后剩一个数, 问这个数最大是多少.

$1 \le n \le 10^5, 0 \le c_i \le 10^9, \sum c_i \ge 1$

不会思考的人有难了!

一开始想的是把某点之后所有的数单独拎出来变成 $0$, 然后 $0$ 往上推. 这样就几个问题. 首先是这个点会不会在同一个数里, 然后是即使往上推, 如果有多的, 我还可以拿出来变成 $0$. 比如 $0, 1, 1, 1, 2$, 可以 $2$ 不动, 但是拿出两个 $1$ 变成 $0$. 还有一个, 不是说要"物尽其用", 有时候可以通过"放弃"来达到更好的结果. 假设有 $4, 5$ 两个数, 虽然我可以变成两个 $0$, 但是如果恰好多出来一个 $0$, 比如说最后变成了 $0, 3$, 然后再做的话答案就是 $2$; 但其实可以"丢弃"一个数, 即取出 $4, 5$, 取 $\rm{mex}$ 为 $0$. 这样就只有一个 $3$ 了.

这些问题都是不会思考导致的, 没有反问一下自己, 真的是这样吗. 以后注意, 一定要多次反问自己.

接下来就说一下正解.

特判 $\sum cnt_i = 1$.

可以想到二分答案 $k$, 如果最后要得到 $k$, 那么 $0 \sim k-1$ 的数至少要有 $1$ 个, 其他随意. 这样的话, 只要取所有数的 $\rm{mex}$ 就行了. 虽然有的数还可以变成 $0$, 但是完全没必要了. $k$ 及之后的数可以变为 $0$, 考虑 $k$ 之前, 从 $k-1$ 向 $2$ 枚举. 为什么这样呢? 从前向后枚举就会出现"不知道后面可不可以拿一些出来变成$0$". 而从后向前枚举就避免了这个问题, 当然这时候就需要统计一个"当前需要值", 去和枚举到的数比较, 而不是像错误的从前向后枚举去直接推结果.

可以发现, 如果 $cnt_{k-1}$ 是 $0$, 那么就需要去凑一个 $k-1$ 出来. 怎么凑呢? 当然是再来一组 $0 \sim k - 2$. 然后会发现, 需要的"组数"是随着枚举而非严格递增的. 假设当前枚举值为 $i (2 \le i < k)$, 设需要的组数为 $need$, 即 $0 \sim i-1$ 至少需要 $need$ 个. 在枚举的过程中, 尝试去维护 $need$: 若 $cnt_i \ge need$, 即能够满足要求, 并且多了 $cnt_i - need$ 个 $i$, 可以变成 $0$; 若 $cnt_i < need$, 即不够满足要求, 还差 $need - cnt_i$ 个 $i$, 那么就需要 $0 \sim i-1$ 各再多 $need - cnt_i$ 个, 即 $need += need - cnt_i$.

注意到 $0$ 和 $1$ 是特殊的, 他们可以相互转换, 所以我们只做到 $2$, 现在的 $need$ 就是, 需要多少个 $0$ 和 $1$. 只要他们个数加起来不小于 $2need$ 即可.

细节, 由于 $need += need - cnt_i$, 会发现 $need$ 是指数级上升的. 而 $cnt_i \le 10^9$, 所以当 $need > 10^14$ 后一定无解 (🌿写题时想错了写的 $10^9$ 但是过了), $10^14$ 是 $10^5$ 个 $10^9$ 都变为 $0$ 算得的. 特判一下.

再一个是二分的上界确定. 由于第 $i$ 数需要 $2^{i-1}$ 个 $0$ 凑出来, 所以我们对 $10^9 \times 2^i$ 求和, 得到不超过 $10^9 \times 2^{n+1}$, 即答案不超过 $\log(10^9 \times 2^{n+1}) < 30n$ (写题时又错了但是A了笑死)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

const int MAXN = 3e6 + 10;	// 注意开 30n

LL a[MAXN], sum = 0, cnt[MAXN];
int n;

bool check(int k) {
	for (int i = 0; i < min(k, n); i++)
		cnt[i] = a[i];
	for (int i = k; i < n; i++)
		cnt[0] += a[i];
	LL need = 1;
	for (int i = k-1; i > 1; i--) {
		if (need > 1e14)
			return false;
		if (cnt[i] < need)
			need += need - cnt[i];
		else
			cnt[0] += cnt[i] - need;
	}
	return cnt[0] + cnt[1] >= need * 2;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", a + i);
		sum += a[i];
	}
	if (sum == 1) {
		for (int i = 0; i < n; i++)
			if (a[i] == 1)
				printf("%d\n", max(1, i));
	}
	else {
		int l = 1, r = 30 * n, ans = -1;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (check(mid)) {
				ans = mid;
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}

就感觉这种思考方式很自然, 但是我想不到, 暂时还没有想明白应该如何"自然地思考", 可能等我搞清楚了会上一个台阶叭, 希望叭.