构造mex(牛客周赛 Round 59)

题目链接；

D-构造mex_牛客周赛 Round 59 (nowcoder.com)

题目描述：

输出和输出描述：

输入样例：

3
6 3 3
7 4 3
6 6 0

输出样例：

NO
YES
4 0 1 2
YES
1 1 1 1 1 1

 分析：

数学思维题，赛后看了一下比率：182/3788。

对n和k的大小进行分类讨论:

n < k

n<k的情况一定输出是0，因为极端的情况下n最多能达到的是0 1 2 ... n - 1，到达不了k - 1，那么第一个没有的整数是: n，就不再是k了。

n == k

这个就是 0 1 2 ... n - 1，又因为n == k, 所以第一个没有的是整数就是n,也即是k，只需要判断前n项和是不是等于s的，也即是 s == (n - 1) * n / 2 ? "YES" : "NO";

例子：

s = 6, n = 4, k = 4

输出的是:

0 1 2 3  

n > k

对k的特殊情况进行讨论：

k == 0

k等于0的情况下，能组成的最小值是 1 * n，如果s小于最小值的话，那就是不可能的输出"NO",否则的话，可以先输出n-1个1，然后最后在输出最后一个 s - (n - 1)即可。

例子：

s = 11, n = 5, k = 0;

那么构造的是: 0 0 0 0 11

k == 1

k等于1的情况下，能组成的最小值是0(n个0)。

但是要注意s等于1就要输出"NO"了，因为我输出n-1个0，最后在输出一个1，但是这个1和k一样，因此我想把这个1换成2或者0，但是发现换为0的那么就需要一个0去加1，换为2的话，就需要一个0减去1，那么就变味负的了，因此输出"NO"

例子:

s = 1, n = 4, k = 1

输出的是: "NO"

s不等于1的时候，可以先输出n-1个0，然后在输出最后一个 s - (n - 1) * 0。

例子:

s = 3, n = 4, k = 1

输出的是: 0 0 0 3 

k == 其他

这个是最复杂的情况了。k等于其他(2, 3, 4, ....)的情况下的最小值是: (0 1 2 .....k - 1 0 0 0 0 0 0 )也即是 (k - 1) * k / 2 + (n - k) * 0，要是当前的s小于这个最小值的话直接输出"NO"。

先去分配0 到 (k - 1)这n个数，那么还剩下和为：s- k * (k - 1) / 2, n - k个数。

贪心的做法：先分配 n - k - 1个0，在把最后一个数的值为s- k * (k - 1) / 2。但是需要注意的是 这个值是不是等于k的。

要是等于k的话就出现了k，我就会让这个最后一个数减去1，然后让1到k-1后面的0 0 0 0 中任意一个0改为1即可，但是需要注意的是，1到k-1的后面有没有0，没有的话就不可以。

例子：

s = 9, n = 4, k = 4

输出的是：

按照之前的思路输出的是 

0 1 2 3 4,但是发现出现了4，因此我就会让4减去1，然后让蓝色部分的一个0加上1，但是发现蓝色部分没有0的出现，因此正确的输出是"NO",那可不可以让红色部分的某一个加1，当然不可以，红色部分某一个加1了，第一个没有的整数就不再是k了。

例子：

s = 9, n =10, k = 4

刚开始构造的是:

0 1 2 3 0 0 0 0 0 4

出现了k，因此我会让蓝色部分的第一个0加1，让最后这个数-1即可，也就是变为了:

0 1 2 3 1 0 0 0 0 3

要是不等于k的话，无论是大于还是小于直接输出即可。

例子：

s = 8, n = 10, k = 4 

输出的是:

0 1 2 3 0 0 0 0 0 2 

代码：

#include<bits/stdc++.h>
#define int long long 
#define endl "\n"using namespace std;signed main() {int t;cin >> t;while(t -- ) {int s, n, k;cin >> s >> n >> k;if(n == k ){if(s != (n - 1) * n / 2) {cout << "NO" << endl;} else {cout << "YES" << endl;for(int i = 0; i < n; i ++ ) {cout << i << " ";}cout << endl;}continue;}if(n < k ) {cout << "NO" << endl;} else {int a[n + 10];if(k == 0) {if(s < 1 * n) {//最小是 n * 1 cout << "NO" << endl;} else {cout << "YES" << endl;for(int i = 1; i <= n - 1; i ++ ) {cout << 1 << " ";}cout << s - (n - 1) << endl;}} else if(k == 1) {if(s == 1) {cout << "NO" << endl;} else {cout << "YES" << endl;for(int i = 1; i <= n - 1; i ++ ) {cout << 0 << " ";}cout << s << endl;}} else {
//				cout << "sum = " << k * (k - 1) / 2 << endl;
//				cout << "s = " << s << endl;// 最小是 k * (k - 1) / 2if(s < k * (k - 1) / 2 + 0 * (n - k)) {cout << "NO" << endl;} else {int b[n + 10];//k个了 for(int i = 0; i <= k - 1; i ++ ) {a[i] = i;}int sum = s - (k - 1) * k / 2;int gs = n - k; // 剩余的个数 //cout << "sum = " << sum << " gs = " << gs << endl;for(int i = 1; i <= gs - 1; i ++ ) {b[i] = 0;}b[gs] = sum;if(sum == k) {if(gs == 1) {cout << "NO" << endl;continue;}b[1] = 1;b[gs] = sum - 1;}cout << "YES" << endl;for(int i = 0; i <= k - 1; i ++ ) {cout << a[i] << " ";}for(int i = 1; i <= gs; i ++ ) {cout << b[i] << " ";}cout << endl;}}}}return 0;
}

 运行结果：