1399A.Remove Smallest
给你一个由 n个正整数(大于零)组成的数组 a� 。
在一次移动中,你可以选择两个索引 i和 j ( i≠j ),使得 ai 和 aj之间的绝对差不大于 1 ( |ai−aj|≤1 ),并移除这两个元素中最小的一个。如果两个元素相等,则可以删除其中任何一个元素(但要恰好删除一个)。
你的任务是找出是否有可能通过几次(可能是零次)这样的移动来得到由1个元素组成的数组。
你必须回答 t个独立的测试案例。
输入
输入的第一行包含一个整数 t� ( 1≤t≤10001≤�≤1000 )–测试用例数。然后是 t� 个测试用例。
测试用例的第一行包含一个整数 n� ( 1≤n≤50 ) - a 的长度。第二行测试用例包含 n个整数 a1,a2,…,an ( 1≤ai≤100),其中 ai 是 i-th 元素。
输出
对于每个测试案例,打印答案:如果可以使用问题陈述中描述的几个(可能是零)移动来获得由个元素组成的数组,则打印 “是”,否则打印 “否”。
例如
输入
5
3
1 2 2
4
5 5 5 5
3
1 2 4
4
1 3 4 4
1
100
输出
YES
YES
NO
NO
YES
注意
在示例的第一个测试案例中,我们可以执行以下一系列动作:
- 选择 i=1和 j=3并删除 ai (因此 a变成 [2;2] );
- 选择 i=1 和 j=2 并删除 aj (于是 a 变成 [2] )。
在示例的第二个测试情形中,我们可以任意选择 i和 j,删除哪个元素并不重要。
在示例的第三个测试情形中,我们无法删除 2 和 4 。
解决方法
// codeforces
// 1399A.Remove Smallest
# include<iostream>
# include<vector>
# include<algorithm>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
int flag = 1, x;
vector<int> a;
for(int j = 0; j < n; j++)
{
cin >> x;
a.push_back(x);
}
sort(a.begin(), a.end());
for(int k = 0; k < n-1; k++)
{
if(abs(a[k] - a[k+1]) > 1)
{
cout << "NO" << endl;
flag = 0;
break;
}
}
if(flag == 1)
{
cout << "YES" << endl;
}
}
return 0;
}