题目大意
对于长度为 $n$ 的排列 $a$，给定如下的冒泡排序的代码：
1 | for (int i = 1; i < n; i++) { |
2 | for (int j = 1; j <= n - i; j++) { |
3 | if (a[j] > a[j + 1]) { |
4 | swap(a[j], a[j + 1]); |
5 | } |
6 | } |
7 | } |
问第 $k$ 次 swap 操作过后的 $a$。
数据范围：$n \le 10^6$。
思路分析
对于每个位置记在它前面大于它的数的个数 $c_i$。我们先计算出第 $k$ 次操作以前总共进行了几轮完整的冒泡。考虑二分答案 $x$，我们要计算 $x$ 轮冒泡之后的 swap 次数。我们发现每一轮，如果某个数前面有比它大的数，那么这个数肯定会向前挪动一步；否则它就不会向前挪动了。而对于每一个数，向前挪动一次就代表 swap 一次。所以，$x$ 轮以后第 $i$ 个数的移动次数就是 $\min { x, c_i }$，总移动次数就是 $\sum_i \min { x, c_i }$。
我们二分出了总共进行了几轮完整的冒泡，接下来只要处理剩下的半轮冒泡即可。考虑先解出若干轮完整冒泡后的数列，假设轮数是 $x$。那么，对于 $c_i \ge x$ 的时候，$a_i$ 会被挪到 $a_{i - c_i}$ 处；对于剩下的所有 $c_i < x$ 的数，我们发现它们之间的相对顺序已经被排好了，我们只要在当前还没有数的位置中从小到大地填入这些数即可。对于剩下的半轮冒泡，我们直接模拟即可。这样的总时间复杂度就是 $O(n \log n)$，可以通过本题。
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | typedef long long ll; |
6 | const int maxn = 1e6; |
7 | int n, a[maxn + 3], b[maxn + 3], c[maxn + 3], d[maxn + 3], m, t[maxn + 3]; |
8 | ll k; |
9 | |
10 | void add(int x) { |
11 | for (int i = x; i; i ^= i & -i) { |
12 | b[i]++; |
13 | } |
14 | } |
15 | |
16 | int sum(int x) { |
17 | int y = 0; |
18 | for (int i = x; i <= n; i += i & -i) { |
19 | y += b[i]; |
20 | } |
21 | return y; |
22 | } |
23 | |
24 | ll solve(int x) { |
25 | ll y = 0; |
26 | for (int i = 1; i <= n; i++) { |
27 | y += min(c[i], x); |
28 | } |
29 | return y; |
30 | } |
31 | |
32 | int main() { |
33 | scanf("%d %lld", &n, &k); |
34 | ll s = 0; |
35 | for (int i = 1; i <= n; i++) { |
36 | scanf("%d", &a[i]); |
37 | c[i] = sum(a[i]); |
38 | add(a[i]); |
39 | s += c[i]; |
40 | } |
41 | if (k > s) { |
42 | puts("Impossible!"); |
43 | return 0; |
44 | } |
45 | int l = 0, r = n, mid; |
46 | while (l < r) { |
47 | mid = (l + r + 1) / 2; |
48 | if (solve(mid) <= k) { |
49 | l = mid; |
50 | } else { |
51 | r = mid - 1; |
52 | } |
53 | } |
54 | k -= solve(l); |
55 | for (int i = 1; i <= n; i++) { |
56 | if (c[i] >= l) { |
57 | d[i - l] = a[i]; |
58 | } else { |
59 | t[++m] = a[i]; |
60 | } |
61 | } |
62 | sort(t + 1, t + m + 1); |
63 | for (int i = 1, p = 1; i <= n; i++) { |
64 | if (!d[i]) { |
65 | d[i] = t[p++]; |
66 | } |
67 | } |
68 | for (int i = 1; k && i < n; i++) { |
69 | if (d[i] > d[i + 1]) { |
70 | swap(d[i], d[i + 1]), k--; |
71 | } |
72 | } |
73 | for (int i = 1; i <= n; i++) { |
74 | printf("%d%c", d[i], " \n"[i == n]); |
75 | } |
76 | return 0; |
77 | } |