A16635. Equal Occurrences
编程题
入门
知识点
题目描述
当且仅当数组中任意元素出现的次数都相等时，我们称这个数组是平衡的。例如，$[1,1,3,3,6,6]$ 和 $[2,2,2,2]$ 都是平衡的，而 $[1,2,3,3]$ 不是平衡的（元素 $1$ 和 $3$ 出现的次数不同）。注意，空数组始终是平衡的。
现给定一个非递减数组 $a$，包含 $n$ 个整数。请你找出其最长平衡子序列的长度$^{\text{∗}}$。
$^{\text{∗}}$若序列 $b$ 可以通过删除 $a$ 中若干（可能为零或全部）任意位置的元素得到，则称 $b$ 为 $a$ 的子序列。
现给定一个非递减数组 $a$，包含 $n$ 个整数。请你找出其最长平衡子序列的长度$^{\text{∗}}$。
$^{\text{∗}}$若序列 $b$ 可以通过删除 $a$ 中若干（可能为零或全部）任意位置的元素得到，则称 $b$ 为 $a$ 的子序列。
输入格式
本题包含多组测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 500$）。接下来的每组用例描述如下：
每组测试用例第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_1\le a_2\le \cdots \le a_n\le n$），表示数组 $a$ 的元素。
每组测试用例第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_1\le a_2\le \cdots \le a_n\le n$），表示数组 $a$ 的元素。
输出格式
对于每组测试用例，输出一个整数，表示数组 $a$ 的最长平衡子序列的长度。
输入输出样例
输入 #1
4 5 1 1 4 4 4 2 1 2 15 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5 5 3 3 3 3 3
输出 #1
4 2 9 5
说明/提示
在第一个测试用例中，整个数组 $a = [1, 1, 4, 4, 4]$ 不是平衡的，因为元素 $1$ 出现了 $2$ 次，元素 $4$ 出现了 $3$ 次，出现次数不同。子序列 $[1, 1, 4, 4]$ 是平衡的，因为 $1$ 和 $4$ 均出现了 $2$ 次。因此，最长平衡子序列的长度为 $4$。
在第二个测试用例中，整个数组 $a = [1, 2]$ 已经是平衡的，因此最长平衡子序列的长度为 $2$。
在第三个测试用例中，最长平衡子序列为 $[1,1,1,2,2,2,3,3,3]$。
在第四个测试用例中，整个数组 $a = [3, 3, 3, 3, 3]$ 已经是平衡的，因此最长平衡子序列的长度为 $5$。
在第二个测试用例中，整个数组 $a = [1, 2]$ 已经是平衡的，因此最长平衡子序列的长度为 $2$。
在第三个测试用例中，最长平衡子序列为 $[1,1,1,2,2,2,3,3,3]$。
在第四个测试用例中，整个数组 $a = [3, 3, 3, 3, 3]$ 已经是平衡的，因此最长平衡子序列的长度为 $5$。