A.发生次数相等

题目重述

给定一个非递减的数组 $a$，长度为 $n$。
定义平衡数组：数组中每个不同的元素出现的次数都相等。
求 $a$ 的最长平衡子序列的长度。

注意：子序列可以不连续，但保持原顺序（本题因为非递减，顺序无关紧要，我们只关心元素种类和频次）。

思路分析

因为数组是非递减的，所以相同的元素一定连续出现。
设数组中有 $k$ 种不同的元素，第 $i$ 种元素出现的次数为 $c_i$，且 $c_1, c_2, \dots, c_k$ 已知。

我们想选一个子序列，使得选中的元素种类中，每种元素出现的次数相同。
换句话说，如果我们选择了 $m$ 种元素，那么每种元素必须选相同的次数 $f$，子序列长度就是 $m \times f$。

关键观察

• 对于每种元素，我们最多能选它的全部出现次数 $c_i$。
• 如果我们决定让每种选中的元素出现 $f$ 次，那么能选这种元素的充要条件是 $c_i \ge f$。
• 所以对于给定的 $f$，我们能选出的元素种类数 = 满足 $c_i \ge f$ 的不同元素的数量。

设 $count[f]$ = 出现次数 $\ge f$ 的元素种类数。
那么长度为 $f \times count[f]$ 的平衡子序列是可行的（从每种满足条件的元素中任选 $f$ 个）。

我们只需枚举 $f$ 从 $1$ 到 $n$（$f$ 不能超过最大出现次数），计算 $f \times count[f]$ 的最大值即可。

算法步骤

1. 遍历数组，统计每种元素的出现次数，存入数组 $freq$（因为非递减，可以边遍历边统计）。
2. 令 $maxf = \max(freq)$。
3. 对 $f$ 从 $1$ 到 $maxf$：
   • 统计 $freq$ 中 $\ge f$ 的个数，记为 $cnt$。
   • 更新答案 $ans = \max(ans, f \times cnt)$。
4. 输出 $ans$。

复杂度：$O(n^2)$ 最坏（$n \le 100$ 完全可行），也可以优化到 $O(n \log n)$，但没必要。

举例验证

例1

$a = [1,1,4,4,4]$
频次：$1$ 出现 $2$ 次，$4$ 出现 $3$ 次。

$f=1$：$\ge 1$ 的种类有 $2$ 种 → 长度 $1 \times 2 = 2$
$f=2$：$\ge 2$ 的种类有 $2$ 种 → 长度 $2 \times 2 = 4$
$f=3$：$\ge 3$ 的种类有 $1$ 种 → 长度 $3 \times 1 = 3$
最大是 $4$，输出 $4$。

例2

$a = [1,2]$
频次：$1$ 出现 $1$ 次，$2$ 出现 $1$ 次。

$f=1$：$\ge 1$ 的种类有 $2$ 种 → 长度 $2$
最大是 $2$，输出 $2$。

例3

$a = [1,1,1,1,1,2,2,2,2,3,3,3,4,4,5]$
频次：$1:5,\ 2:4,\ 3:3,\ 4:2,\ 5:1$

$f=1$：种类 $5$ → 长度 $5$
$f=2$：种类 $4$（1,2,3,4） → 长度 $8$
$f=3$：种类 $3$（1,2,3） → 长度 $9$
$f=4$：种类 $2$（1,2） → 长度 $8$
$f=5$：种类 $1$（1） → 长度 $5$
最大是 $9$，输出 $9$。

题解代码（对应标程思路）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 统计频次
        vector<int> freq;
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (a[i] == a[i - 1]) {
                cnt++;
            } else {
                freq.push_back(cnt);
                cnt = 1;
            }
        }
        freq.push_back(cnt);

        int maxf = *max_element(freq.begin(), freq.end());
        int ans = 0;

        for (int f = 1; f <= maxf; f++) {
            int kinds = 0;
            for (int c : freq) {
                if (c >= f) kinds++;
            }
            ans = max(ans, f * kinds);
        }

        cout << ans << "\n";
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \times \text{maxf})$，最坏 $O(n^2)$，$n \le 100$ 完全可行。
• 空间复杂度：$O(n)$。

总结

本题的核心是枚举“每种元素出现的次数”$f$，然后看有多少种元素能达到这个次数，乘起来就是该 $f$ 下能获得的最长平衡子序列长度，最后取最大值。
因为数组非递减，统计频次很方便，且 $n$ 很小，直接枚举即可。