C—袋鼠将军的神秘序列

题目有以下细节：

输入的元素不能 > n；
输入的元素中 > 0 的元素出现的次数不能超过 1 次；
将 > 0 的元素选出来，升序排序，第 1 个元素不能超过 2，即不能是 3 及以上的数；
排除以上情况，那么我们知道排序完的序列肯定是严格递增的，是公差为 1 的等差数列（首项要么是 1，要么是 2 ），可以允许最多缺少一项，不能缺少两项及以上！

以下样例都是无解：

6
0 0 10 0 0 0

6
0 0 2 2 0 0

6
0 0 3 4 5 0

6
0 1 4 5 6 0  // 差值不能超过 1，记住：是公差为 1 的等差数列！最多只能缺少 1 项！！！

6
0 1 3 4 6 0

完整程序，有点丑

,,ԾㅂԾ,,

void solve(){
   int n;
   cin>>n;
   vector<pair<int,int>> a;
   map<int,int> mp;
   bool sign=1;
   for(int i=1;i<=n;i++){
       int x;
       cin>>x;
       if(x>0)a.emplace_back(x,i),mp[x]++;
       if(x>n)sign=0;
   }
   for(auto [x,y]:mp){
       if(y>=2){
           sign=0;
           break;
       }
   }
   sort(a.begin(),a.end());
   int mex=1,flag=0,idx=-1;
   for(int i=0;i<a.size();i++,mex++){
       if(a[i].first != mex){
           if(a[i].first != mex+1){
               sign=0;
               break;
           }
           mex++;
           if(flag)sign=0;
           flag=1;
       }
       if(flag)idx=a[i].second;
   }
   if(!sign){
       cout<<"-1\n";
       return ;
   }
   
   if(a.size()==1){
       if(a[0].first >= 3){
           cout<<"-1\n";
           return ;
       }
       cout<<a[0].first<<"\n";
       while(a[0].first--){
           cout<<a[0].second<<" ";
       }
       cout<<"\n";
       return ;
   }
   
   if(flag)cout<<a.size()+1<<"\n";
   else cout<<a.size()<<"\n";
   mex=1;
   for(int i=0;i<a.size();i++,mex++){
       if(mex!=a[i].first){
           mex=a[i].first;
           cout<<idx<<" ";
       }
       cout<<a[i].second<<" ";
   }
   cout<<"\n";
}

题解 | #袋鼠将军的神秘序列#

C—袋鼠将军的神秘序列