← 返回题目列表

Codeforces · 2242/B

B. 主频划分

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,其中包含数字 $$$1$$$、$$$2$$$ 和 $$$3$$$。检查是否可以将其分成三部分 连续非空 部分,使得对于从 $$$1$$$ 到 $$$3$$$ 的每个部分 $$$i$$$,满足以下条件:

  • 大于 $$$i$$$ 的元素数量最多为该部分的一半。

也就是说,你需要将数组 $$$a$$$ 分成三对不相交的 连续非空 部分,以便在左侧部分中 1 的数量至少为 2 和 3 的总数,在中间部分中 1 和 2 的总数至少为 3 的数量,而右侧部分可以是任何内容,但必须非空。

例如,数组 $$$[2, 1, 1, 3, 3, 1, 2, 3]$$$ 可以分为三部分:$$$[2, 1, 1, 3]$$$、$$$[3, 1, 2]$$$ 和 $$$[3]$$$。并且数组 $$$[2, 1, 3, 3, 3, 2, 3]$$$ 不能以这种方式拆分。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^{5}$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_{i}$$$ ($$$1 \le a_{i} \le 3$$$)。

输入数据的附加约束:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,打印 是 如果存在一种根据需要分割数组的方法,并且 NO 否则。

无论如何,您都可以打印答案。例如, 是的, 是, NO, nO 也将被接受。

示例

输入
复制

10
8
2 1 1 3 3 1 2 3
7
2 1 3 3 3 2 3
4
1 3 3 2
6
2 2 2 1 1 1
8
3 2 1 2 1 1 2 3
3
2 1 2
3
1 2 3
5
1 3 3 1 1
5
1 1 3 3 1
3
1 3 1

输出
复制

YES
NO
NO
NO
YES
NO
YES
YES
YES
NO

注意

声明中解释了前两个测试用例。

在第三个测试用例中,左侧部分可能是 $$$[1]$$$,但是中间部分的任何选择($$$[3]$$$、$$$[3, 3]$$$、$$$[3, 3, 2]$$$)都不起作用。左边部分也可能是$$$[1, 3]$$$;那么中间部分一定是$$$[3, 2]$$$,在这种情况下,右边部分是空的。因此,第三个例子的答案是 NO.

在第四个测试用例中,唯一有效的左侧部分是整个数组,因为在任何非空较短前缀上,1 的数量小于 2 的数量,因此中间部分和右侧部分不能同时为非空。

在第五个测试用例中,分割 $$$[3, 2, 1, 2, 1, 1], [2], [3]$$$ 有效。

在第六个测试用例中,唯一可能的分割是 $$$[2], [1], [2]$$$,但左侧部分不起作用。

在第七个测试用例中,分割 $$$[1], [2], [3]$$$ 有效。

在第八个测试用例中,分割 $$$[1, 3], [3, 1], [1]$$$ 有效。

在第九个测试用例中,分割 $$$[1], [1], [3, 3, 1]$$$ 有效。

在第十个测试用例中,唯一可能的分割是$$$[1],[3],[1]$$$,但中间部分不起作用。