首页 > 试题广场 >

小O的数组染色

[编程题]小O的数组染色
  • 热度指数：312 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小P给了小O一个长为 n 的数组 a_1,a_2,\dots,a_n ，初始数组中的每个数字都是白色。小O可以进行如下操作：
  • 选择一个区间 [l,r] ，满足 a_l = a_r ，将区间所有元素染红。
小O想知道她最少几次操作可以将所有数字都染红，请你帮帮他吧。

输入描述:
每个测试文件均包含多个测试点。第一行输入一个整数 T\ (1\le T\le 10^4) 代表测试数据组数，每组测试数据描述如下：
第一行输入一个整数 n\ (1 \leq n \leq 2\cdot 10^5) 表示数组 a 的长度。
第二行输入 n 个整数 a_1,a_2,\dots,a_n\ (1 \leq a_i \leq 10^9) 表示数组 a_i 的元素。
除此之外，保证所有的 n 的之和不超过 2 \cdot 10^5 。


输出描述:
对于每一个测试点，在一行上输出一个正整数，表示染红所有数字的最小操作次数。
示例1

输入

2
5
1 2 3 1 2
3
1 2 3

输出

2
3

说明

对于第一组测试数据
2次操作即可，第一次选择：l = 1, r = 4，第二次选择：l = 2, r = 5。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

贪心 OPPO 哈希
难度：
0条回答 232浏览

热门推荐

相关试题

小O的数组染色

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号