CF1772C

FiraCode · 2022-12-20 19:56:03 · 题解

思路

可以想到，用贪心的方法，每次相隔 1,2,3...。

那么当当前这个数增加了间隔的数之后，剩余的数字加上以前的数字不足 k 的话，就只能把剩下的间隔都变成 1。

例如 n=4,k=3

1. 第一个数是 1。
2. 第二个数，与前一个间隔 1,是 2。
3. 第三个数，因为 2+2=4，所以这个数间隔完之后，就没有数字了（因为要 \le n，且要严格递增），所以就变成间隔一个，是 3。

CODE:

#include <bits/stdc++.h>
using namespace std;
int T;
int k, n;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &k, &n);
        printf("%d ", 1);
        bool flag = false;
        int tempk = k;
        --k;
        int id = 1, last = 1, t = 0;
        for (int i = 1; i < tempk; ++i) {
            int temp = last + id;
            if (flag) {//间隔都是1
                printf("%d ", ++t);
                continue;
            }
            if (temp > n) {//超过了值域
                flag = true;
                t = last + 1;
                printf("%d ", t);
                continue;
            }
            if (n - temp + 1 < k) {//即使其他的间隔只有一也不足k个数，即剩下的所有的都是前一个+1，都还是会在第k个数时超过值域，那么从这个开始，以后就是间隔是1
                flag = true;
                t = last + 1;
                printf("%d ", t);
                continue;
            }
            printf("%d ", temp);//否则输出这个数
            --k;//剩余的数字个数减一
            last = temp;
            id++;//间隔加一
        }
        puts("");
    }
    return 0;
}