构造mex个人题解/详细思路C++

题目：有三个数字s、n、k。
有一个整数s，你需要做的是将他分为n个非负整数，使得这n个整数之和恰好为s，并且N个数中未出现的最小非负整数为K。请写出代码解决这个问题

思路:
这道题乍一看并不难，题目要求只是尽量凑一个符合条件的数字组合。首先需要明确要将s拆成n个数字并且不包含k。且k为未出现过最小。则证明无特殊情况下0——k-1必须要全部出现。那么当0——k-1全出现一次后，我们跳过k。则此时满足了最小未出现整数为k。此时计算0——k-1的总和sum。s减去这个sum得到还需要拼凑的数字。但要注意，我们只有n个位置可以使用，你已经使用了k个位置来占0——k-1。也就是说你现在只剩n-k个位置可以填数字。但好在你保持住了k最小的条件，所以你大概率可以直接将所差的数字填入后补0到n位，因为只有当差的数字正好为k时填入才会不满足条件。
那么恰好还差k怎么办？
很简单，对于数字x来说除了x=1以外的任何时候都可以由1和(x-1)凑出，也就是说当正好差k且不等于1时，有两个空位即可凑成（n-k>=2即可）。当巧的不能再巧的正好差k且等于1时，此时无论如何也凑不出了，因为要保证1为最小未出现位，而现在差1，能凑的只有0，而再多0的和也是0，凑不出1。

还是很难说明白，直接配合代码。

#include<iostream>
#include<algorithm>
#include<iomanip>

using namespace std;
typedef long long llint;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    llint t;
    cin >> t;
    while(t--){
        llint s,n,k;
        cin >> s >> n >> k;
      	//要满足题意则k以前的整数至少出现一次，即0~k-1。一共k位
      	//所以位子不够(n<k)或者刚好够但没凑出s((n-1)*n/2!=s)则直接NO
        if(n<k||(n==k&&(n-1)*n/2!=s)){
            cout << "NO" << endl;
            continue;
        }
        llint a=n-k;//还剩的位子
        llint b=s-((k-1)*k/2);//满足k最小未出现后还需要凑的数
      	//如果如果位置没满就凑齐了则直接NO
      	//你可能会疑惑为什么补0不行
      	//因为首先要求k个位置0~k-1的和，若这没站满就凑出s则凑不出k最小未出现
        if(b<0){
            cout << "NO" << endl;
            continue;
        }
      	//常规情况：剩一个不为0不为k的数字，则直接放进去补0即可
        if(b!=k&&k!=0){
            cout << "YES" << endl;
            llint i=0;
            for(i=0;i<k;i++)cout << i << " ";
            for(;i<n-1;i++)cout << 0 << " ";
          	//要注意有可能这个差为0则不需要放进去。
          	//例如3 3 3 结果为0 1 2在第一个for中已经齐了，这里自然是0，舍
            if(i==n-1)
            cout << b << endl;
            else cout << endl;
            //cout << 1 << endl;
            continue;
        }
      	//特殊情况1：最小未出现为0
      	//此时不可使用补0策略，可用补1最后补总差的策略
        if(k==0){
            if(s<n)cout << "NO" << endl;//如果s连分出n个1都做不到直接NO
            else{
                cout << "YES" << endl;
                for(llint i=0;i<n-1;i++)cout << 1 << " ";//补1直到最后一个位置
                cout << s-(n-1) << endl;//补上总差
                //cout << 2 << endl;
            }
            continue;
        }
      	//特殊情况2：差为k且k为1
      	//这种情况下不可能凑了
        if(b==k&&k==1){
            cout << "NO" << endl;
            continue;
        }
      	//特殊情况3：差为k
        if(b==k){
            if(a<2)cout << "NO" << endl;//上面说了此时需要至少两个空位
            else{
                cout << "YES" << endl;
                llint i=0;
                for(i=0;i<k;i++)cout << i << " ";//先输出0~k-1
              	//补0
                for(;i<n-2;i++){
                    cout << 0 << " ";
                }
              	//和第正常情况下的判断意图一样
                if(i==n-2)
                cout << 1 << " " << k-1 << endl;//补上1和n-1凑出k
                else cout << endl;
                //cout << 3 << endl;
            }
        }
    }
  	//圆满结束！！！
    return 0;
}

题解 | #构造mex#

构造mex个人题解/详细思路C++

还是很难说明白，直接配合代码。