F. 数组缩减 题解

---

一、题意理解

给定一个长度为 $n$ 的数组 $a$。每次操作可以移除若干个元素，要求这些元素满足：

• 要么全部相等；
• 要么两两互不相等。

对每个目标大小 $x$（$0 \leq x \leq n-1$），求将数组恰好缩减到 $x$ 的最小操作次数。

---

二、问题转化

转化一：求每轮最多能移除多少元素

原问题求"达到某个大小所需最少操作次数"，等价于求"在 $k$ 次操作内，最多能移除多少元素"。

设 $f(k)$ 表示在恰好 $k$ 次操作下最多能移除的元素数，则 $c_x$ 就是满足 $f(k) \geq n - x$ 的最小 $k$。且 $f(k)$ 单调不减，可以通过求 $f(k)$ 的前缀最优来得到所有答案。

---

转化二：压缩频次数组

由于元素的具体值不重要，只关心每种值的出现次数。设频次数组 $C[1..n]$，其中 $C_i$ 表示值 $i$ 在原数组中出现的次数。只保留 $C_i > 0$ 的项，排序后得到长度为 $m$ 的非降数组 $c$。

---

三、操作的本质

一次操作对应两种模式：

• 类型一（全局减）：从每种出现过的值中各移除一个元素，即将所有非零 $c_i$ 减 $1$（但不低于 $0$）。
• 类型二（消除最大）：移除某个值的全部出现，即将某个 $c_i$ 清零。

由此，$k$ 次操作由 $x$ 次"全局减"和 $y$ 次"消除最大"组成（$x + y = k$）。且操作顺序不影响最终结果。

---

四、关键观察

假设固定 $y$（消除了 $y$ 个频次最大的元素），那么剩余的频次都会受到 $x$ 次全局减的影响。

设未消除的频次中最大值为 $M$，则 $x$ 超过 $M$ 没有意义（再多减只会使已为 $0$ 的项保持为 $0$），所以有效的 $x$ 只取 $c$ 中出现的值。

由于 $c$ 中仅有 $O(m)$ 个不同的值，整个 $(x, y)$ 对的枚举量实际为 $O(n)$。

---

五、算法流程

1. 读入数组 $a$，统计频次，得到数组 $c$（只含 $> 0$ 的项），排序。

2. 初始化答案数组 $res[s] = \infty$，表示移除 $s$ 个元素的最少操作数。

3. 枚举 $k$（全局减的次数 $x$ 取 $c$ 中的值递增）：

   • 用指针 $j$ 维护第一个满足 $c_j > k$ 的位置。前 $j$ 个频次 $\leq k$，会被完全清零；后续频次减去 $k$。

   • 令 $i$ 从 $j$ 遍历到 $m$，其中 $i$ 表示第一个不被消除最大的元素的索引。这里的 $i$ 对应消除最大的次数 $y = m - i$。

   • 对于一个确定的 $(k, i)$，操作总次数为：

     $$d = k + (m - i)$$

     移除的总元素数为：

     $$s = \underbrace{\sum_{t=j}^{i-1} (c_t - k)}_{\text{前 } i-j \text{个会受全局减影响的部分}} + \underbrace{\text{被消除最大的部分之和}}_{\text{会在后续用前缀和计算}} $$

     但标程的循环逻辑里，$s$ 是通过累加 $(c_i - k)$ 得到的，维护的是在消除 $m-i$ 个最大频次后，剩余部分受全局减减少的元素数。

   • 对于每个计算出的移除量 $s$，用 $d$ 更新 $res[s]$。

4. 最后对 $res$ 取前缀最小值：$res[i] = \min(res[i], res[i-1])$，保证单调性。

---

六、标程详细解析

private fun solveTest() {
    val n = readInt()
    val a = readInts(n)
    val c = intarr(n)
    for (x in a) {
        c[x - 1]++
    }
    val res = intarr(n, Int.MAX_VALUE)
    c.sort()
    var j = 0
    for (k in 0..n) {
        while (j < n && c[j] <= k) j++
        var s = 0
        for (i in j..n) {
            val d = k + (n - i)
            if (s < n)
                res[s] = min(res[s], d)
            if (i < n) s += (c[i] - k)
        }
    }
    for (i in 1 .. n - 1) {
        res[i] = min(res[i], res[i - 1])
    }
    println(res)
}

步骤拆解：

1. 构建频次数组 $c$：长度为 $n$，$c[x-1]++$ 统计值 $x$ 的出现次数。排序后得到非降序列。

2. 外层循环 $k$：$k$ 从 $0$ 到 $n$，表示全局减的次数。$k$ 不会超过 $n$（因为数组大小只有 $n$）。

3. 指针 $j$：c[j] <= k 的频次在 $k$ 次全局减下会归零，$j$ 是第一个 $> k$ 的位置。

4. 内层循环 $i$：$i$ 从 $j$ 到 $n$，$n - i$ 表示消除最大的次数。

   • $d = k + (n - i)$：总操作次数 = 全局减次数 + 消除最大次数。
   • $s$：维护当前方案下移除的元素总数（逐步累加各频次被减掉的部分）。
   • 用 $d$ 更新 $res[s]$。

5. 前缀最小值：因为如果能用 $d$ 次操作移除 $s$ 个元素，那么移除少于 $s$ 个元素也可以用不超过 $d$ 次操作完成。

---

七、答案的还原

$res[s]$ 存储的是移除 $s$ 个元素所需的最少操作数。

原问题要求输出 $c_x$——缩减到恰好 $x$ 个元素的最少操作数，即移除 $n - x$ 个元素。

因此最终输出为 $res[n], res[n-1], \dots, res[1]$（即 $c_0 = res[n]$，$c_1 = res[n-1]$，...）。

---

八、复杂度分析

• 构建频次数组 $O(n)$。
• 排序频次数组 $O(n \log n)$。
• 双指针枚举 $(k, i)$ 总复杂度 $O(n)$，因为每个频次只被访问有限次。
• 总时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

所有测试用例 $\sum n \leq 3 \times 10^5$，算法完全可行。

---

九、代码实现（C++）

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> freq(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        freq[a[i] - 1]++;
    }
    
    vector<int> c;
    for (int i = 0; i < n; i++) {
        if (freq[i] > 0) c.push_back(freq[i]);
    }
    sort(c.begin(), c.end());
    int m = c.size();
    
    vector<int> res(n + 1, n + 1);  // res[s] = min ops to remove s elements
    res[0] = 0;
    
    int j = 0;
    for (int k = 0; k <= n; k++) {
        while (j < m && c[j] <= k) j++;
        int s = 0;
        for (int i = j; i <= m; i++) {
            int d = k + (m - i);  // total operations
            if (s <= n) {
                res[s] = min(res[s], d);
            }
            if (i < m) s += (c[i] - k);
        }
    }
    
    // 前缀取 min，保证单调性
    for (int i = 1; i <= n; i++) {
        res[i] = min(res[i], res[i - 1]);
    }
    
    // 输出 c_0 到 c_{n-1}，即 res[n] 到 res[1]
    for (int x = 0; x < n; x++) {
        cout << res[n - x] << " \n"[x == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

十、样例验证（以第一个样例为例）

数组：$[5,5,5,5,2,2,2,8,6,1,7]$，$n=11$。

频次排序后：$c = [1,1,1,1,3,4]$（对应值 $1,6,7,8,2,5$ 的出现次数）。

经算法计算得到的 $res$ 前缀最小值后，输出 $c_0$ 到 $c_{10}$ 依次为：

3 3 2 2 2 1 1 1 1 1 1

与题目示例完全一致。