連結
如果只利用「目前最大值」對逆序數對的貢獻，原題可以轉化成 : 在到裡面挑一些數使得他們的和，可以用數歸證明一定可以達成，而構造這個問題的解只需要貪心的由大的往小的選就好了。
再轉回原題，可以利用「目前最大值」選一個數；用「目前最小值」跳過一個數。
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #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];
}
}
|