Codeforces Global Round 9 C. Element Extermination (思维,栈)

题意:有一个长度\(n\)的序列,如果\(a_{i}<a_{i+1}\),那么可以选择删除\(a_{i}\)或者\(a_{i+1}\),再继续操作,问是否能够将序列删到只剩一个元素.
题解:感觉这种序列变化的题目能用stack写,所以用数组模拟stack写了一发.

首先,假如栈为空或者\(a_{i}<a_{i-1}\),那么就让\(a_{i}\)入栈.

否则,如果栈中元素只有1个,那么我们不用做任何操作,若不止1个,让当前元素入栈,循环判断,如果栈中元素个数>2,那么我们删除小的(即\(a_{i-1}\),因为要确保删除后大的要比前面的大,这样才能继续删),而如果元素个数=2,那么我们删除大的(因为要确保前面的这个小的要比后面的大的数小),最后看栈中元素个数是否为1即可.

代码:

int t;

int n;

int x;

int stk[N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);

  	cin>>t;

  	 while(t--){

  	 	cin>>n;

  	 	int cnt=0;

  	 	 for(int i=1;i<=n;++i){

  	 	 	cin>>x;

  	 	 	if(cnt==0) stk[++cnt]=x;

  	 	 	else if(stk[cnt]<x){

  	 	 		if(cnt!=1){

  	 	 			stk[++cnt]=x;

  	 	 			while(stk[cnt]>stk[cnt-1]){

  	 	 				if(cnt==2) cnt--;

  	 	 				else if(cnt>2){

  	 	 					int tmp=stk[cnt];

  	 	 					stk[--cnt]=tmp;

  	 	 				}

  	 	 				else if(cnt==1) break;

  	 	 			}

  	 	 		}

  	 	 	}

  	 	 	else stk[++cnt]=x;

  	 	 }

  	 	 if(cnt==1) cout<<"YES"<<endl;

  	 	 else cout<<"NO"<<endl;

  	 }

    return 0;

}

巴特西

Codeforces Global Round 9 C. Element Extermination (思维,栈)

最新文章

热门文章