A14868 | Vlad and Candies
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Not so long ago, Vlad had a birthday, for which he was presented with a package of candies. There were $n$ types of candies, there are $a_i$ candies of the type $i$ ( $1 \le i \le n$ ).
Vlad decided to eat exactly one candy every time, choosing any of the candies of a type that is currently the most frequent (if there are several such types, he can choose any of them). To get the maximum pleasure from eating, Vlad does not want to eat two candies of the same type in a row.
Help him figure out if he can eat all the candies without eating two identical candies in a row.
Vlad decided to eat exactly one candy every time, choosing any of the candies of a type that is currently the most frequent (if there are several such types, he can choose any of them). To get the maximum pleasure from eating, Vlad does not want to eat two candies of the same type in a row.
Help him figure out if he can eat all the candies without eating two identical candies in a row.
输入格式
The first line of input data contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of input test cases.
The following is a description of $t$ test cases of input, two lines for each.
The first line of the case contains the single number $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of types of candies in the package.
The second line of the case contains $n$ integers $a_i$ ( $1 \le a_i \le 10^9$ ) — the number of candies of the type $i$ .
It is guaranteed that the sum of $n$ for all cases does not exceed $2 \cdot 10^5$ .
The following is a description of $t$ test cases of input, two lines for each.
The first line of the case contains the single number $n$ ( $1 \le n \le 2 \cdot 10^5$ ) — the number of types of candies in the package.
The second line of the case contains $n$ integers $a_i$ ( $1 \le a_i \le 10^9$ ) — the number of candies of the type $i$ .
It is guaranteed that the sum of $n$ for all cases does not exceed $2 \cdot 10^5$ .
输出格式
Output $t$ lines, each of which contains the answer to the corresponding test case of input. As an answer, output "YES" if Vlad can eat candy as planned, and "NO" otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
输入输出样例
输入 #1
6 2 2 3 1 2 5 1 6 2 4 3 4 2 2 2 1 3 1 1000000000 999999999 1 1
输出 #1
YES NO NO YES YES YES
In the first example, it is necessary to eat sweets in this order:
- a candy of the type $2$ , it is the most frequent, now $a = [2, 2]$ ;
- a candy of the type $1$ , there are the same number of candies of the type $2$ , but we just ate one, now $a = [1, 2]$ ;
- a candy of the type $2$ , it is the most frequent, now $a = [1, 1]$ ;
- a candy of the type $1$ , now $a = [0, 1]$ ;
- a candy of the type $2$ , now $a = [0, 0]$ and the candy has run out.
In the second example, all the candies are of the same type and it is impossible to eat them without eating two identical ones in a row.
In the third example, first of all, a candy of the type $2$ will be eaten, after which this kind will remain the only kind that is the most frequent, and you will have to eat a candy of the type $2$ again.
- a candy of the type $2$ , it is the most frequent, now $a = [2, 2]$ ;
- a candy of the type $1$ , there are the same number of candies of the type $2$ , but we just ate one, now $a = [1, 2]$ ;
- a candy of the type $2$ , it is the most frequent, now $a = [1, 1]$ ;
- a candy of the type $1$ , now $a = [0, 1]$ ;
- a candy of the type $2$ , now $a = [0, 0]$ and the candy has run out.
In the second example, all the candies are of the same type and it is impossible to eat them without eating two identical ones in a row.
In the third example, first of all, a candy of the type $2$ will be eaten, after which this kind will remain the only kind that is the most frequent, and you will have to eat a candy of the type $2$ again.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted