洛谷 U139014 大使人选
题目背景
SeawaySeawa**y所效命的AlphaAlpha国和邪恶的EulerEuler国之间关系并不好，为了应付二国之间越来越频繁的外交交涉，AlphaAlpha国不得不更换一个更加能干的驻EulerEuler国特命全权大使。AlphaAlpha国人民委员会任命SeawaySeawa**y为外交部长，全面负责挑选合适的大使人选......
题目描述
大使应聘会上，SeawaySeawa**y面前站着清一色的NN名美女。(不是SeawaySeawa**y只选美女，是只有美女报名)。每名美女有一个美貌值b_ib**i。SeawaySeawa**y要从中挑选一位来出任大使。由于都是美女，SeawaySeawa**y要细细比较，不能大咧咧地刷掉长得太丑的。他的挑选策略是：每次挑出两名美貌值相差小于等于1的美女，并刷掉其中美貌值较小的。现在，SeawaySeawa**y想知道，他是否能够通过若干次挑选操作，挑出唯一的大使人选？
输入格式
从文件embassador.inembassado**r.i**n中读入数据。
第一行一个整数tt，表示测试数据组数。每组测试数据的第一行是一个整数NN，第二行是NN个整数，描述每个美女的美貌值b_ib**i。
输出格式
输出到文件embassador.outembassado**r.out中。
对于每组数据，输出YESYES和NON**O来回答SeawaySeawa**y的问题。
命题背景：
加强了一下数据范围，我觉得10×105就挺大了，但是事实证明还可以更大。但是好像到不了106了，大约4×10^5吧。
而且10^5还能稍微欺骗一下选手，以为是log算法。
其实没啥问题啊，排序的确是log的。
题解：
一开始想奇偶，但很容易发现和奇偶无关。
于是我们想探究性质：由于每次删除较小值，所以最后剩下的一定是最大值。
而且一定是从小到大一个一个删除，要是跳跃了，就会出现有些点删不下去。
比如，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;
}