题目描述
思维决定代码!!
我是真的想不到什么清晰的办法,然后我用的是分类讨论的思想:
经过一顿分析:结果就只能是3种:0,1,2
首先,把n==2的情况特殊处理掉,因为后面的讨论给漏掉了(第一发失败的原因)
序列中是否有0?
-
没有0:ans=0
-
有0:继续往下讨论
记0的数量为n, 大于0的数量为m,是否有 m>=n-1 ?
- 是: ans=0 (可以用大于0的数,去插空,使得mex()=0 )
- 否:继续下一轮判断
序列中是否有1?
- 没有1,ans=1 (无1,mex必须得是1)
- 有1,继续往下判断
是否有大于1的数?
- 有,ans=0 (用大于1的数跟0接近,使得 mex=1)
- 没有,ans=2
总结
真正实战的时候思路并没有这么清晰,很紧张,很乱的那种
这种是属于蛮办法,但是目前我只能想得到他
C++ 代码
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
int k;
cin>>k;
bool y0=false,y1=false,y2=false;
int n=0,m=0;
for(int i=0; i<k; i++){
int a;
cin>>a;
if(a==0) {n++; y0=true;}
else{
m++;
if(a==1) y1=true;
if(a>1) y2=true;
}
}
if(y0){
if(m>=n-1) puts("0");
else{
if(y1){
if(y2) puts("1");
else puts("2");
}
else puts("1");
}
}
else puts("0");
}
return 0;
}