原题呈现

01 的冒泡排序#

题目描述#

01 学习了冒泡排序，觉得太简单，于是创造了属于自己的排序方式．

给定一个长度为 $n$ 的排列 $a$ 以及一个神秘数字 $k$ ，01 会执行以下操作：

初始令 $cnt = 0$ ．
如果当前数组已经排好序（即非降序），则停止操作．
否则，按 $i$ $i$ 从 $1$ $1$ 到 $n - k + 1$ $n - k + 1$ 遍历：
- 若子区间 $a_i, a_{i+1}, \ldots, a_{i+k-1}$ 并非升序，则将该区间从小到大排序，同时令 $cnt = cnt + 1$ ．
一轮结束，回到第二步．（这一步时题解作者增加的，或许加上会更严谨一些？）

你需要求出操作结束时 $cnt$ 的值．

输入格式#

第一行输入两个整数 $n, k$ ，表示数组长度和神秘数字．第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ，表示给定的排列．

输出格式#

输出一行一个整数，表示最终的 $cnt$ 值．

样例#

输入样例 1#

输出样例 1#

1
5

数据范围#

对于 $20\%$ 的数据，保证 $n \le 2000$ ．
对于另 $10\%$ 的数据，保证 $k = 2$ ．
对于另 $20\%$ 的数据，保证 $\forall 1 \le i \le k,\ a_i = i$ ．
对于 $100\%$ $100%$ 的数据：
- $1 \le n \le 2 \times 10^5$
- $2 \le k \le n$

我们回忆冒泡排序的过程，实际上，冒泡排序每一次可以让未排序的最大的一个数归位，那么变种有没有这种性质呢？

我们尝试模拟这个流程，首先，对区间 $[1,k]$ 排序，然后，丢下了最小的一个数，区间右移到 $[2, k+1]$ ．显然，此时区间内， $[2,k]$ 里面存放的是 $[1,k]$ 中前 $k-1$ 大的 $k-1$ 个数．将其扩展到 $i$ ，当遍历到区间 $[i, i+k-1]$ 时，其中的 $[i,i+k-2]$ 是 $[1, i+k-2]$ 中最大的 $k-1$ 个数．

我们来转向结束条件．题目中的结束条件是：

如果当前数组已经排好序（即非降序），则停止操作．

显然，我们不能对于每一个数，都将它和前一个数比较，这样不好维护．我们知道，一个数组是有序的当且仅当每个数前面都没有比它大的数，因此，我们定义 $b_i$ 表示位置 $i$ 之前比 $a_i$ 大的数．这样，结束条件就从“有序”转化为了 $\forall i,b_i=0$ ． $b_i$ 可以使用树状数组快速算出．

那要如何才能使得 $b_i$ 减小呢？我们在每一次区间右移时，区间左边的 $k-1$ 个数都是有序的，只有最后一个数是无序的．因此，这就相当于将最后一个数插入到前面这个序列中．此时 $b_i$ 变化如下：

若 $b_i > k-1$ ，由于当前区间只有 $k$ 个数，且前 $k-1$ 个数是当前已遍历到的最大的 $k-1$ 个数．又因为比 $i$ 大的至少也有 $k$ 个．因此，这表示 $i$ 是当前区间内最小的数，将 $i$ 的位置前移 $k-1$ ，即 $b_i\to b_i-k+1$ ．
若 $b_i \leq k-1$ ，由于比 $b_i$ 小的数最多也只有 $k-1$ 个，那么这 $b_i$ 个全在当前区间里了．这说明将当前区间进行一次排序就足以把所有比 $a_i$ 大的数移动到 $a_i$ 后面了，此时， $a_i$ 前面已经没有比 $a_i$ 小的数了，故 $b_i\to 0$ ．

综上所述， $i$ 需要移动 $\lceil\frac{b_i}{k-1}\rceil$ 次才能移动到目标位置．当然，所有最后一次移动到区间 $[1,k]$ 的数可以一次性全部排序使其回到正确的位置．故若设 $t_1=\lceil\frac{b_i}{k-1}\rceil$ ， $t_2$ 表示当前点每一次移动 $k-1$ 移动到区间 $[1,k]$ 需要移动的次数：

若 $t_1 \leq t_2$ ，则表示 $i$ 根本不会移动到 $[1,k]$ ，或是移动到时 $b_i$ 已经为 0，不需要集体排序．
若 $t_1>t_2$ ，则表示 $i$ 在进行了 $t_2$ 次移动后，移动到了 $[1,k]$ ，由于每一轮每一个数字最多只能移动 $k-1$ 步一次，故此时已经过去 $t_2$ 轮．会在第 $t_2+1$ 轮预定一次 $[1,k]$ 的集体排序．

特别的，一开始就在 $[1,k]$ 的数若 $b_i\neq 0$ ，则会在第一轮 $[1, k]$ 的集体排序中恢复有序．

对于每一项计算移动次数加和即可．

标程

1
#include <bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
const int N = 2e5 + 100;
5
int n, k;
6
int a[N]；
7
bool sfa[N];
8
// sfa => Sort in the First Action in i th round，是否需要在第 i 轮在区间 [1,k] 进行排序
9

10
struct BIT {
11
    int f[N];
12
    void Modify(int pos, int v) {
13
        for (int i = pos; i <= n; i += (i & (-i))) {
14
            f[i] += v;
15
        }
16
    }
17
    int query(int pos) {
18
        if (pos == 0)
19
            return 0;
20
        int ans = 0;
21
        for (int i = pos; i >= 1; i -= (i & (-i))) {
22
            ans += f[i];
23
        }
24
        return ans;
25
    }
26
    int query(int l, int r) { return query(r) - query(l - 1); }
27
} bit;
28

29
signed main() {
30
    ios::sync_with_stdio(false);
31
    cin.tie(0);
32
    cout.tie(0);
33
    cin >> n >> k;
34
    for (int i = 1; i <= n; i++) {
35
        cin >> a[i];
36
    }
37
    long long cnt = 0;
38
    for (int i = 1; i <= k; i++) {
39
        int b = bit.query(a[i], n);
40
        if (b != 0) {
41
            sfa[1] = true;
42
        }
43
        bit.Modify(a[i], 1);
44
    }
45
    for (int i = k + 1; i <= n; i++) {
46
        int b = bit.query(a[i], n);
47
        bit.Modify(a[i], 1);
48
        int t1 = ceil(1.0 * b / (k - 1.0));
49
        int t2 = ceil((i - k + 0.0) / (k - 1.0));
50
        if (t1 <= t2) {
51
            cnt += t1;
52
        } else {
53
            cnt += t2;
54
            sfa[t2 + 1] = true;
55
        }
56
    }
57
    for (int i = 1; i <= n; i++)
58
        cnt += sfa[i];
59
    cout << cnt;
60
    return 0;
61
}

音乐

音乐

01 的冒泡排序#

题目描述#

输入格式#

输出格式#

样例#

输入样例 1#

输出样例 1#

数据范围#

文章分享

音乐

安吉D16 T4

01 的冒泡排序#

题目描述#

输入格式#

输出格式#

样例#

输入样例 1#

输出样例 1#

数据范围#

文章分享