← 返回题目列表

Codeforces · 1646/B

B. 质量与数量

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

$$$ \def\myred#1{\color{red}{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $$$ $$$\def\RED{\myred{红色}} \def\BLUE{\myblue{蓝色}}$$$

给你一个 $$$n$$$ 非负整数序列 $$$a_1, a_2, \ldots, a_n$$$。最初,序列的所有元素都未绘制。您可以绘制每个数字 $$$\RED$$$ 或 $$$\BLUE$$$(但不能同时绘制),或者不绘制。

对于颜色 $$$c$$$,$$$\text{Count}(c)$$$ 是用该颜色绘制的序列中的元素数量,$$$\text{Sum}(c)$$$ 是用该颜色绘制的序列中的元素之和。

例如,如果给定序列是 $$$[2, 8, 6, 3, 1]$$$ 并且它是这样绘制的: $$$[\myblue{2}, 8, \myred{6}, \myblue{3}, 1]$$$ (其中 $$$6$$$ 被漆成红色,$$$2$$$ 和 $$$3$$$ 被漆成蓝色, $$$1$$$ 和 $$$8$$$ 未绘制)则 $$$\text{Sum}(\RED)=6$$$、$$$\text{Sum}(\BLUE)=2+3=5$$$、$$$\text{Count}(\RED)=1$$$ 和 $$$\text{Count}(\BLUE)=2$$$。

确定是否可以绘制序列,使得 $$$\text{Sum}(\RED) > \text{Sum}(\BLUE)$$$ 且 $$$\text{Count}(\RED) < \text{Count}(\BLUE)$$$。

输入

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

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 10^9$$$) - 给定序列。

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

输出

对于每个测试用例,如果可以绘制满足上述要求的给定序列,则打印 YES,否则打印 NO。

在任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。

示例

输入 #1

4
3
1 2 3
5
2 8 6 3 1
4
3 5 4 2
5
1000000000 1000000000 1000000000 1000000000 1000000000

输出 #1

NO
YES
NO
NO

注意

在第一个测试用例中,无法绘制序列。例如,如果您按以下方式绘制序列: $$$[\myblue{1},\myblue{2},\myred{3}]$$$(其中 $$$3$$$ 绘制为红色,$$$1$$$ 和 $$$2$$$ 绘制为蓝色),则 $$$\text{Count}(\RED)=1 < \text{Count}(\BLUE)=2$$$,但是$$$\text{总和}(\RED)=3 \ngtr \text{总和}(\BLUE)=3$$$。因此,这不是绘制序列的可能方法。

在第二个测试用例中,语句中描述了绘制序列的可能方法。我们可以看到 $$$\text{Sum}(\RED)=6 > \text{Sum}(\BLUE)=5$$$ 和 $$$\text{Count}(\RED)=1 < \text{Count}(\BLUE)=2$$$。

在第三个测试用例中,无法绘制序列。例如,如果您按以下方式绘制序列: $$$[\myred{3},\myred{5},\myblue{4}, \myblue{2}]$$$ (其中 $$$3$$$ 和 $$$5$$$ 绘制为红色,$$$4$$$ 和 $$$2$$$ 绘制为蓝色),则 $$$\text{Sum}(\RED) = 8 > \text{Sum}(\BLUE) = 6$$$ 但 $$$\text{Count}(\RED) = 2 \nless \text{Count}(\BLUE) = 2$$$。因此,这不是绘制序列的可能方法。

在第四个测试用例中,可以证明没有可能的方法来绘制满足总和和计数约束的序列。