P15400 [NOISG 2026 Prelim] Hungry Cats

依旧水题解。

思路

题面过于诡异，此后的描述中用单位代指猫，大小代指快乐值。
先将所有单位按照快乐值大小排序。
首先注意到每个单位只能吞一次，所以第二大的只能被最大的吞掉。
就算有和它一样大的，在吞掉更小的之后比它更大，此时也无法再次吞单位，故无法吞掉它。
所以以此类推，所有单位都只能被比它大的第一个单位吞掉。
故从小到大枚举，从第三小的开始枚举，如果有两个单位相差一（吞前一个后相等）或相等（吞前一个后更大），则输出 NO 并 return 0;，否则输出 YES。
对于第一小的，它不会吞任何其它单位，故只判断最小的两个是否相等。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=2e5+47;
int n,h[N];
signed main(){
	read(n);
	rep(i,1,n){
		read(h[i]);
	}
	sort(h+1,h+n+1);
	if(h[2]==h[1]){
		puts("NO");
		return 0;
	}
	rep(i,3,n){
		if(h[i]-h[i-1]<=1){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
}