A.Nezzar and Colorful Balls
生肉{:target=”_blank”}
题目翻译
$\text{Nezzar}$ 有 $n$ 个球,编号依次为 $1, 2, \cdots, n$。
数字 $a _ 1, a _ 2, \cdots, a _ n$ 依次写在这些球上。
这些数字是非递减的,即对于任意的 $1 \leq i < n$,有 $a _ i \leq a _ i + 1$。
$\text{Nezzar}$ 想用最少的颜色将这些球涂色,但需要满足如下要求:
- 对于每种颜色的球,这些球上的编号必须严格单调递增。
注意,长度为 $1$ 的序列也被认为严格单调递增。
请帮 $\text{Nezzar}$ 计算他最少需要多少种颜色。
输入
第一行包含一个正整数 $t \ (1 \leq t \leq 100)$,表示测试数据组数。
对于每组测试数据:
第一行包含一个正整数 $n \ (1 \leq n \leq 100)$。
第二行包含 $n$ 个正整数 $a _ 1, a _ 2, \cdots, a _ n \ (1 \leq a _ i \leq n)$。
输出
对于每组测试数据,输出 $\text{Nezzar}$ 需要的最少的颜色数量。
样例输入
5
6
1 1 1 2 3 4
5
1 1 2 2 3
4
2 2 2 2
3
1 2 3
1
1
样例输出
3
2
4
1
1
算法
(暴力枚举) $O(tn)$
因为所有球的编号是非递减的,因此我们只需要将编号相同的球,涂上不同的颜色即可。
那么答案也就是每个 $a _ i$ 出现的数量的最大值。
注意数据中 $a _ i$ 的范围是 $1 \leq a _ i \leq n$,因此可以将所有 $a _ i$ 扔入一个数组中,最后枚举求最大值。
这个做法的时间和空间复杂度都是 $O(n)$ 的。
注意数据中 $a _ i$ 是非递减的,因此可以使用双指针,枚举所有 $a _ i$ 出现的次数。
这个做法的时间复杂度是 $O(n)$ 的,但是可以将空间复杂度优化至 $O(1)$。
这里给出第二种做法的代码。
时间复杂度
每个数都会被遍历一次,所以总时间复杂度是 $O(tn)$。
C++ 代码
#include <cstdio>
#include <cstring>
const int N = 105;
int task;
int n, a, x, res;
int main()
{
scanf("%d%d", &task, &n);
while (task -- )
{
res = 1;
for (int i = 0, j; i < n; i = j)
{
if (!i) scanf("%d", &a);
j = i + 1, scanf("%d", &x);
while (j < n && x == a) scanf("%d", &x), j ++ ;
if (j - i > res) res = j - i;
a = x;
}
printf("%d\n", res);
n = x; // 最后会多读进来一个 x,这个 x 就是下一组数据的 n
}
return 0;
}