思路:
既然不能改变顺序,那么我们就可以从第一个开始枚举,选择最优的高度(与前一个的高的差最小)。
如果当前已经不能组成不上升序列了,那么就直接输出 “ NO ”
详细代码的解释看注释
AC CODE:
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,x,y,first=1000000001;//n 为数的个数,x ,y 分别为高度与宽度,first 需要定义一个大数,以免第一个数就已经不能存放
cin>>n;
for(int i=1;i<=n;i++){
cin>>x>>y;
if(x>first&&y>first){//当两个数都比前一个数大(不能组成不上升序列)
cout<<"NO\n";//直接输出
return 0;//结束程序
}
else if(x>first)first=y;//x 比前一个大,则只能选择 y
else if(y>first)first=x;//y 比前一个大,则只能选择 x
else first=max(x,y);//都比前一个数小,则选择最大的
}
cout<<"YES\n";//可以形成不上升序列,输出
return 0;//结束程序
}