题解 | 牛牛的构造

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using vi = vector<int>;
int f(int cnt) {
    int sum = 0;
    cnt--;
    while (cnt) {
        sum++;
        cnt/=2;
    }
    return sum;
}

void solve() {
    int n, k;cin >> n >> k;
    int t = 1;
    int sum = 0;
    while (t <= n) {
        sum += n - t;
        t *= 2;
    }
    if (sum < k) {
        cout << -1 << endl;return;
    }
    vi st(n + 1);
    int cnt = n;
    sum = 0;
    while (cnt > 0) {
        while (1) {
            if (sum + f(cnt) <= k) {
                break;
            }
            cnt--;
        }
        int tt = f(cnt);
        st[cnt] = 1;
        cout << cnt << " ";
        sum += f(cnt);
        cnt--;
    }
    for (int i = 1;i <= n;i++) {
        if (st[i] == 0)cout << i << " ";
    }
}


/*

*/


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

先考虑大于多少数是无解的，那肯定是从大到小的排列是最多的，考虑每个数字的贡献，1贡献0,2贡献1,3贡献2,4贡献2,5贡献3，因为5可以跟1 3 4配对，刚好差值是4 2 1，得出跟二进制有关系，得到计算贡献函数

int f(int cnt) {
    int sum = 0;
    cnt--;
    while (cnt) {
        sum++;
        cnt/=2;
    }
    return sum;
}

然后从大到小，根据贡献从前往后填数字，当前值总贡献值+当前数贡献>k的时候,就cnt--换更小的数，如果是<=就直接输出这个数，然后标记这个数访问过。最后从小到大输出未访问的数字，这些数字不会影响最后的贡献