#CW48. 凸序列(convex)
凸序列(convex)
题目描述
小 W 手中有一个长度为 的整数多重集合。他想把这些数排成序列 ,使每个内部位置都满足
请判断是否存在这样的排列。
输入格式
第一行一个整数 。接下来描述 组数据。每组数据第一行一个整数 ,第二行给出 个整数 。
输出格式
对于每组数据,若存在满足条件的排列,输出 YES,否则输出 NO。
样例 1 输入
3
4
0 3 4 6
4
5 4 1 4
6
1 2 3 4 5 6
样例 1 输出
YES
NO
YES
样例 2 输入
2
4
0 1 1 1
8
0 2 4 6 8 10 12 14
样例 2 输出
NO
YES
样例 3 输入
2
15
0 1 1 1 2 3 4 5 6 7 8 9 10 11 12
15
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70
样例 3 输出
NO
YES
样例 4 输入
2
7
1 1 1 1 1 1 1
7
3 6 9 12 15 18 21
样例 4 输出
YES
YES
样例 5 输入
2
10
0 1 1 1 1 2 3 4 5 6
10
0 10 20 30 40 50 60 70 80 90
样例 5 输出
NO
YES
数据范围
所有数据满足 、、,且单个输入文件中所有 的总和不超过 。
本题采用子任务捆绑计分。每个正式输入文件包含多组数据。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 3 | ||
| 2 | 4 | 每组数据满足 | |
| 3 | 7 | 每组数据满足 | |
| 4 | 5 | 若存在合法排列,则存在满足 的合法排列 | |
| 5 | 17 | 所有数据的 之和不超过 | |
| 6 | 10 | 所有数据的 之和不超过 | |
| 7 | 13 | 所有数据的 之和不超过 | |
| 8 | 9 | 所有数据的 之和不超过 | |
| 9 | 18 | 所有 | |
| 10 | 14 | 无额外限制 |