versin1 ——题目链接
题意：给定一个数列，你可以选择让某个元素+2，或者让相等的两个相邻元素一起+1，问最终能否使得n个元素相等。输出YES / NO
（1<=n<=2e5）
思路：输出YES / NO 的题大胆猜思路就好。 对于第i个元素，如果第i+1号元素和它相加为偶数，也就是奇偶性相同，那么a[i] a[i+1]可以变成任意一个不小于他们中最大值的元素，类似于（）这种括号匹配 。
所以我们用栈来记录。模拟这个匹配过程，最终栈内元素最多只能有1个，也就是其他的匹配对可以任意变大 ，栈内剩余元素也+2，最终相等。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int n;
stack<int> s;
//如果i 和i+1的元素相差为偶数，那么i i+1可以变成任意一个大于等于自己的元素，所以可以不管它
//最终栈里面只能剩下一个元素
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);scanf("%d",&n);for(int i = 1; i <= n ; i++) {
int t;scanf("%d",&t);if(s.size() && (s.top() + t) % 2 == 0) s.pop();else s.push(t);}if(s.size()<=1) puts("YES");else puts("NO");return 0;
}
version2——题目链接
题意：给定一个数列，你可以选择让相等的两个相邻元素一起+1，问最终能否使得n个元素相等。输出YES / NO
(1<=n<=2e5)
思路：这题和上题相比少了让某个元素+2这个条件,其实思路差不多，也是用栈
匹配的条件由奇偶性相同变成二者大小相等，更苛刻一些。
而且有2种情形一定是NO的，
第一是栈内存在i使得，a[i] <a[i+1] ，因为a[i]没有与之匹配的，所以不能变大。
第二种是如果最终栈内剩余元素为1，并且这个剩余的元素小于最大值，它也无法变大。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int n;
stack<int> s;
//i和i+1号元素相等 就可以出栈
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);scanf("%d",&n);int mmax=-1;int flag=1;for(int i = 1; i <= n ; i++) {
int t;scanf("%d",&t);if(s.size()){
if(s.top()<t) flag=0;//一定不行的情况else if(s.top()==t) s.pop();//匹配成功else s.push(t);}else s.push(t);mmax=max(mmax,t);//记录最大值}if(s.size()>1 || (s.size()==1 && s.top()<mmax)) flag=0;if(flag) puts("YES");else puts("NO");return 0;
}