题解：AT_abc143_f [ABC143F] Distinct Numbers

Aurora5090 · 2026-09-15 00:15:19 · 题解

提供一个 O(n) 的线性做法，和题解区的另一个线性做法本质一样，写起来也很简洁。

有两个必要条件，合起来会变成充要条件：

1. 如果有 N' 个可用元素，那么最多可以分出 r = \lfloor N'/K \rfloor 组。
2. 如果一个数字出现了 c 次，那么它至多出现在 c 个组里;
   如果目前只能分出 r 个组，那么这种数字只能提供 \min(c, r) 个可用元素。

我们循环迭代这两个条件，直到它们都满足，此时的组数就是答案：

  int all = n, r = n; // all 表示可用元素数量 N'
  for (int k = 1; k <= n; k++) {
    while (all / k < r) { // 直到条件 1 和 2 同时满足
      all -= cnt[r];
      r--;
    }
    cout << (all / k) << '\n';
  }

注意代码里的 \text{cnt}_i 表示有多少颜色的数量 \ge i。完整代码。

严格的正确性说明依赖 Gale–Ryser 定理，可以看这个 推销。

具体原理是把这种分组视作二分图，要求：

• 左部图每个点的度数均为 K；
• 右部每个点 i 代表一个颜色，度数不超过其出现次数。

给定了对左右部度数的限制，判断这个二分图是否可以被构造。

Gale-Ryser 定理说，要满足左部有 X 个度数为 K 的节点，右部度数的共轭序列 \text{cnt}_i 必须满足对于 x = 1,2 \dots X，均有：

而由于此处 \text{cnt}_i 不增，故上式左侧的前缀和 f(x) 是上凸的，我们只要检查 f(X) 处是否满足即可。