309224: CF1646B. Quality vs Quantity

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Quality vs Quantity

题意翻译

给定一个长度为 $n$ 的数列 $a_1,a_2,\cdots,a_n$。你可以将数列中的某些元素涂成红色或者蓝色。请判断是否有一个涂色方案,使得被涂成红色的元素的和大于被涂成蓝色的元素的和,且被涂成红色的元素个数小于被涂成蓝色的元素个数。 数据范围: - $t$ 组数据,$1\leqslant t\leqslant 1000$。 - $3\leqslant n,\sum n\leqslant 2\times 10^5$。 - $0\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC

题目描述

$ \def\myred#1{\color{red}{\underline{\bf{#1}}}} \def\myblue#1{\color{blue}{\overline{\bf{#1}}}} $ $ \def\RED{\myred{Red}} \def\BLUE{\myblue{Blue}} $ You are given a sequence of $ n $ non-negative integers $ a_1, a_2, \ldots, a_n $ . Initially, all the elements of the sequence are unpainted. You can paint each number $ \RED $ or $ \BLUE $ (but not both), or leave it unpainted. For a color $ c $ , $ \text{Count}(c) $ is the number of elements in the sequence painted with that color and $ \text{Sum}(c) $ is the sum of the elements in the sequence painted with that color. For example, if the given sequence is $ [2, 8, 6, 3, 1] $ and it is painted this way: $ [\myblue{2}, 8, \myred{6}, \myblue{3}, 1] $ (where $ 6 $ is painted red, $ 2 $ and $ 3 $ are painted blue, $ 1 $ and $ 8 $ are unpainted) then $ \text{Sum}(\RED)=6 $ , $ \text{Sum}(\BLUE)=2+3=5 $ , $ \text{Count}(\RED)=1 $ , and $ \text{Count}(\BLUE)=2 $ . Determine if it is possible to paint the sequence so that $ \text{Sum}(\RED) > \text{Sum}(\BLUE) $ and $ \text{Count}(\RED) < \text{Count}(\BLUE) $ .

输入输出格式

输入格式


Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 1000 $ ). Description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 3\le n\le 2\cdot 10^5 $ ) — the length of the given sequence. The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 0\le a_i\le 10^9 $ ) — the given sequence. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式


For each test case, print YES if it is possible to paint the given sequence satisfying the above requirements, and NO otherwise. You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

输入输出样例

输入样例 #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

说明

In the first test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: $ [\myblue{1},\myblue{2},\myred{3}] $ (where $ 3 $ is painted red, $ 1 $ and $ 2 $ are painted blue) then $ \text{Count}(\RED)=1 < \text{Count}(\BLUE)=2 $ , but $ \text{Sum}(\RED)=3 \ngtr \text{Sum}(\BLUE)=3 $ . So, this is not a possible way to paint the sequence. In the second test case, a possible way to paint the sequence is described in the statement. We can see that $ \text{Sum}(\RED)=6 > \text{Sum}(\BLUE)=5 $ and $ \text{Count}(\RED)=1 < \text{Count}(\BLUE)=2 $ . In the third test case, there is no possible way to paint the sequence. For example, if you paint the sequence this way: $ [\myred{3},\myred{5},\myblue{4}, \myblue{2}] $ (where $ 3 $ and $ 5 $ are painted red, $ 4 $ and $ 2 $ are painted blue) then $ \text{Sum}(\RED) = 8 > \text{Sum}(\BLUE) = 6 $ but $ \text{Count}(\RED) = 2 \nless \text{Count}(\BLUE) = 2 $ . So, this is not a possible way to paint the sequence. In the fourth test case, it can be proven that there is no possible way to paint the sequence satisfying sum and count constraints.

Input

题意翻译

给定一个长度为 $n$ 的数列 $a_1,a_2,\cdots,a_n$。你可以将数列中的某些元素涂成红色或者蓝色。请判断是否有一个涂色方案,使得被涂成红色的元素的和大于被涂成蓝色的元素的和,且被涂成红色的元素个数小于被涂成蓝色的元素个数。 数据范围: - $t$ 组数据,$1\leqslant t\leqslant 1000$。 - $3\leqslant n,\sum n\leqslant 2\times 10^5$。 - $0\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC

加入题单

上一题 下一题 算法标签: