题目大意:
给定一个数组a,如果a[i]<a[i+1],你可以删除其中一个
经过任意次该操作后能否使得数组中只有一个元素。
思路:
一、使用栈去模拟该过程
1、如果栈空,将元素进栈;
2、栈非空,栈顶元素大于输入元素,输入元素进栈
3、栈非空,栈顶元素小于输入元素,
(1)栈中只有一个元素,跳过输入元素,保持栈顶元素最小,否则将输入元素进栈
(2)取出栈顶的两个元素进行比较,将较小的元素删除,留着较大的去继续匹配剩下的元素,特判一下特殊情况。
二、如果第一个元素小于最后一个元素,即可输出YES
AC Code:
#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
stack<int>s;
int n, a;
cin>>n;
for(int i=1; i<=n; i++){
cin>>a;
if(s.empty())
s.push(a);
else if(s.top()>a)
s.push(a);
else{
if(s.size()==1)
continue;
else
s.push(a);
while(1){
int x=s.top(); s.pop();
int y=s.top(); s.pop();
if(y<x)
{
if(s.size()>=1)
s.push(x);
else
s.push(y);
}
else{
s.push(y);
s.push(x);
break;
}
if(s.size()==1)
break;
}
}
}
if(s.size()==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Comments | NOTHING