CSES Inverse Inversions 題解

連結

如果只利用「目前最大值」對逆序數對的貢獻，原題可以轉化成 : 在$0$到$n-1$裡面挑一些數使得他們的和$=k$，可以用數歸證明一定可以達成，而構造這個問題的解只需要貪心的由大的往小的選就好了。
再轉回原題，可以利用「目前最大值」選一個數；用「目前最小值」跳過一個數。

code:

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    i64 K;
    cin >> n >> K;
    for (int l = 1, r = n; n--; ) {
        if (K >= n) {
            cout << r--;
            K -= n;
        }
        else
            cout << l++;
        cout << " \n"[n == 0];
    }
}