A15023. Social Distance
编程题
普及/提高-
知识点
题目描述
$m$ chairs are arranged in a circle sequentially. The chairs are numbered from $0$ to $m-1$ . $n$ people want to sit in these chairs. The $i$ -th of them wants at least $a[i]$ empty chairs both on his right and left side.
More formally, if the $i$ -th person sits in the $j$ -th chair, then no one else should sit in the following chairs: $(j-a[i]) \bmod m$ , $(j-a[i]+1) \bmod m$ , ... $(j+a[i]-1) \bmod m$ , $(j+a[i]) \bmod m$ .
Decide if it is possible to sit down for all of them, under the given limitations.
More formally, if the $i$ -th person sits in the $j$ -th chair, then no one else should sit in the following chairs: $(j-a[i]) \bmod m$ , $(j-a[i]+1) \bmod m$ , ... $(j+a[i]-1) \bmod m$ , $(j+a[i]) \bmod m$ .
Decide if it is possible to sit down for all of them, under the given limitations.
输入格式
The input consists of multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 5 \cdot 10^4$ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ ( $2 \leq n \leq 10^5$ , $1 \leq m \leq 10^9$ ) — the number of people and the number of chairs.
The next line contains $n$ integers, $a_1$ , $a_2$ , ... $a_n$ ( $1 \leq a_i \leq 10^9$ ) — the minimum number of empty chairs, on both sides of the $i$ -th person.
It is guaranteed that the sum of $n$ over all test cases will not exceed $10^5$ .
The first line of each test case contains two integers $n$ and $m$ ( $2 \leq n \leq 10^5$ , $1 \leq m \leq 10^9$ ) — the number of people and the number of chairs.
The next line contains $n$ integers, $a_1$ , $a_2$ , ... $a_n$ ( $1 \leq a_i \leq 10^9$ ) — the minimum number of empty chairs, on both sides of the $i$ -th person.
It is guaranteed that the sum of $n$ over all test cases will not exceed $10^5$ .
输出格式
For each test case print "YES" (without quotes) if it is possible for everyone to sit down and fulfil the restrictions, and "NO" (without quotes) otherwise.
You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).
You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).
输入输出样例
输入 #1
6 3 2 1 1 1 2 4 1 1 2 5 2 1 3 8 1 2 1 4 12 1 2 1 3 4 19 1 2 1 3
输出 #1
NO YES NO YES NO YES
说明/提示
Test case $1$ : $n>m$ , so they can not sit down.
Test case $2$ : the first person can sit $2$ -nd and the second person can sit in the $0$ -th chair. Both of them want at least $1$ empty chair on both sides, chairs $1$ and $3$ are free, so this is a good solution.
Test case $3$ : if the second person sits down somewhere, he needs $2$ empty chairs, both on his right and on his left side, so it is impossible to find a place for the first person, because there are only $5$ chairs.
Test case $4$ : they can sit in the $1$ -st, $4$ -th, $7$ -th chairs respectively.
Test case $2$ : the first person can sit $2$ -nd and the second person can sit in the $0$ -th chair. Both of them want at least $1$ empty chair on both sides, chairs $1$ and $3$ are free, so this is a good solution.
Test case $3$ : if the second person sits down somewhere, he needs $2$ empty chairs, both on his right and on his left side, so it is impossible to find a place for the first person, because there are only $5$ chairs.
Test case $4$ : they can sit in the $1$ -st, $4$ -th, $7$ -th chairs respectively.