概述

本题要求将 ~N~ 个球通过单次改色操作变为全部同色，求最少操作次数。核心解法是保留当前出现次数最多的颜色不变，将其他所有球改为该颜色，答案为 ~N~ 减去最大出现次数。

分析

核心观察

若最终所有球颜色相同，则必然至少有一种颜色在最终状态下出现 ~N~ 次。初始时该颜色已经存在一定数量，只需将其他颜色的球改为该颜色即可，操作次数等于非该颜色的球数。要使操作次数最少，应选择初始出现次数最多的颜色作为目标颜色。

思路

统计每种颜色 ~v~ 的初始出现次数 ~\text{cnt}[v]~。若选择颜色 ~v~ 作为最终颜色，需要将除它以外的 ~N - \text{cnt}[v]~ 个球全部改成 ~v~，因此操作次数为 ~N - \text{cnt}[v]~。在所有颜色中取最大值 ~M = \max\limits_v \text{cnt}[v]~，则最小操作次数为：

$$\displaystyle N - M $$

由于颜色范围是 ~1~ 到 ~N~，只需遍历所有颜色统计即可。

具体示例

样例 ~1~：~N=4~，颜色序列 3 1 2 1。统计：颜色 ~1~ 出现 ~2~ 次，颜色 ~2~ 出现 ~1~ 次，颜色 ~3~ 出现 ~1~ 次，颜色 ~4~ 出现 ~0~ 次。最大出现次数 ~M=2~，答案 ~4-2=2~。
样例 ~2~：全为 ~3~，~M=5~，答案 ~0~。
样例 ~3~：序列 4 2 3 3 4 1 2 7 1，~N=9~。统计：颜色 ~1~ 出现 ~2~ 次，~2~ 出现 ~2~ 次，~3~ 出现 ~2~ 次，~4~ 出现 ~2~ 次，~7~ 出现 ~1~ 次，其余 ~0~ 次。最大 ~M=2~，答案 ~9-2=7~。

算法步骤

1. 读入整数 ~N~ 和长度为 ~N~ 的颜色数组。
2. 创建计数数组 cnt，大小为 ~N~（颜色编号从 ~1~ 到 ~N~）。
3. 遍历每个颜色 ~c~，将 cnt[c-1] 增加 ~1~。
4. 找出 cnt 中的最大值 max_cnt。
5. 输出结果 ~N - max\_cnt~。

复杂度分析

• 时间：~O(N)~，统计和求最大值均为线性。
• 空间：~O(N)~，用于计数数组。

实现注意事项

• 颜色编号可能不是连续出现的，但范围不超过 ~N~，因此数组大小设为 ~N~ 即可，索引用 ~c-1~。
• 输入规模小（~N \le 100~），无需特殊优化。
• 结果一定非负，因为最大出现次数至少为 ~1~（~N \ge 1~）。

源代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> cnt(N, 0);
    for (int i = 0; i < N; ++i) {
        int c;
        cin >> c;
        cnt[c - 1]++;
    }
    int max_cnt = 0;
    for (int v : cnt) {
        max_cnt = max(max_cnt, v);
    }
    cout << N - max_cnt << '\n';
    return 0;
}

import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    N = int(data[0])
    C = list(map(int, data[1:1+N]))
    cnt = [0] * N
    for c in C:
        cnt[c - 1] += 1
    max_cnt = max(cnt)
    print(N - max_cnt)

if __name__ == "__main__":
    solve()