2014 Yandex.Algorithm Elimination Stage, Round 2 D - Inversions

問題文

解法

長さを最小化するので，N * (N - 1) / 2 >= K && (N - 1) * (N - 2) / 2 < K となる最小の N を求める．
あとは，上から順に，その位置の値を変えなければならないところまで順番に 1 から埋めていく．
その場所まで来たら，変えないと行けない数字と swap して，残りの後ろの数を降順に並べるだけ．

コード読んだほうが早い．いつものやつだし．

計算量は O(NlogN)

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int K;
    cin >> K;

    int sz = 1;
    while(sz * (sz - 1) / 2 < K) ++sz;

    vector<int> ans(sz);
    iota(begin(ans), end(ans), 1);
    for(int i = 0; i < sz; ++i) {
        const int sz2 = sz - i;
        const int offset = K - (sz2 - 1) * (sz2 - 2) / 2;
        if(offset > 0) {
            swap(ans[i], ans[i + offset]);
            sort(begin(ans) + i + 1, end(ans));
            reverse(begin(ans) + i + 1, end(ans));
            break;
        }
    }

    cout << sz << endl;
    for(int i = 0; i < sz; ++i) {
        cout << ans[i] << " \n"[i + 1 == sz];
    }
}