CF1399A Remove Smallest
CF1399A Remove Smallest
题目描述
You are given the array aa consisting of nn positive (greater than zero) integers.
In one move, you can choose two indices ii and jj ( i \ne ji=j ) such that the absolute difference between a_ia**i and a_ja**j is no more than one ( |a_i - a_j| \le 1∣a**i−a**j∣≤1 ) and remove the smallest of these two elements. If two elements are equal, you can remove any of them (but exactly one).
Your task is to find if it is possible to obtain the array consisting of only one element using several (possibly, zero) such moves or not.
You have to answer tt independent test cases.
输入格式
The first line of the input contains one integer tt ( 1 \le t \le 10001≤t≤1000 ) — the number of test cases. Then tt test cases follow.
The first line of the test case contains one integer nn ( 1 \le n \le 501≤n≤50 ) — the length of aa . The second line of the test case contains nn integers a_1, a_2, \dots, a_na1,a2,…,a**n ( 1 \le a_i \le 1001≤a**i≤100 ), where a_ia**i is the ii -th element of aa .
输出格式
For each test case, print the answer: "YES" if it is possible to obtain the array consisting of only one element using several (possibly, zero) moves described in the problem statement, or "NO" otherwise.
题意翻译
给你一个 nn 个整数的数列,你可以每次选择满足一下条件的两个位置 i,ji,j :
- i≠ji=j
- |a_i-a_j| \le 1∣a**i−a**j∣≤1
然后删除 a_i,a_ja**i,a**j 中较小的那一个。
问能否通过若干次操作将数列删除到只剩一个数。
题解:
一开始想奇偶,但很容易发现和奇偶无关。
于是我们想探究性质:由于每次删除较小值,所以最后剩下的一定是最大值。
而且一定是从小到大一个一个删除,要是跳跃了,就会出现有些点删不下去。
比如,4 5 6。肯定要先删除4再删除5,如果删除5,4就无法删除。
于是就是个排序。
枚举所有位置和它上面的位置,如果相差小于等于1,就把满足条件次数+1,最后只需要看次数是否是n-1即可。
数据范围完全可以再大。
代码:
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=110;
int n,cnt;
int a[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<n;i++)
if(a[i]==a[i+1]||a[i]+1==a[i+1])
cnt++;
puts(cnt==n-1?"YES":"NO");
}
return 0;
}
相关文章
- Write operations are not allowed in read-only mode (FlushMode.MANUAL): Turn your Session into FlushMode.COMMIT/AUTO or remove 'readOnly' marker from transaction definition.
- Remove Nth Node From End of List
- leetcode 之Remove Duplicates from Sorted Array(2)
- 如果是除去末尾特定字符或字符串:TrimEnd方法性能优于Remove方法
- (LeetCode 82)Remove Duplicates from Sorted List II
- [Transducer] Make an Into Helper to Remove Boilerplate and Simplify our Transduce API
- Navigation bar - remove recent object
- SAP IBASE hierarchy remove - step2 handling
- Angular Remove me测试应用的工作原理
- leetcode 题解 || Remove Nth Node From End of List 问题
- leetcode 83. Remove Duplicates from Sorted List
- std::remove_if