Element Extermination

发布于 2020-07-07  0 次阅读


题目大意:

Element Extermination

给定一个数组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;
}

平平无奇的大学在读本科生