[USACO19JAN] Sleepy Cow Sorting G

题意

给出一个 $1..N$ 的排列。

每次操作只能把当前最前面的那头奶牛拿出来，向后移动若干步，再插入到后面某个位置。

要求用最少操作次数把整个序列变成升序，并输出每次需要后移多少步。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据直接模拟。
// 每次把队首奶牛插入到当前序列中合适的位置，直到整个序列有序。

bool is_sorted_vec(const vector<int> &a) {
    int m = (int) a.size();
    for (int i = 0; i + 1 < m; i++) {
        if (a[i] > a[i + 1]) {
            return false;
        }
    }
    return true;
}

int suffix_start(const vector<int> &a) {
    int n = (int) a.size();
    int start = n - 1;
    while (start > 0 && a[start - 1] < a[start]) {
        start--;
    }
    return start;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> answer;

    while (!is_sorted_vec(a)) {
        int start = suffix_start(a);
        int x = a[0];
        a.erase(a.begin());

        // 删除队首后，前面仍然保留 start-1 头未处理奶牛。
        // 再把 x 插到后缀有序段里第一个 >= x 的位置前面。
        int pos = start - 1;
        while (pos < (int) a.size() && a[pos] < x) {
            pos++;
        }

        answer.push_back(pos);
        a.insert(a.begin() + pos, x);
    }

    cout << answer.size() << '\n';
    for (int i = 0; i < (int) answer.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << answer[i];
    }
    cout << '\n';

    return 0;
}

brute.cpp 直接按题意模拟：只要序列还没排好，就拿出队首奶牛，把它插入到当前序列里第一个不小于它的位置前面。

这个过程很好理解，但如果真的用数组做插入，复杂度会到 $O(N^2)$ 。

关键观察是：从后往前看，原序列中总会有一段最长严格递增后缀，这一段奶牛的相对顺序已经正确，不需要主动操作。

设这段后缀从 $start$ 开始，那么：

最少操作次数就是 $start - 1$
前面的奶牛必须按顺序一个个拿出来插入到这段有序部分中

接下来只剩一个问题：第 $i$ 头前缀奶牛应该后移多少步？

它被拿出来以后：

前面还会保留 $start - i - 1$ 头尚未处理的前缀奶牛
后面是一个已经有序的集合

所以它应插入的位置，就是：

未处理前缀数量
加上 有序集合里比它小的元素数量

第二部分可以用树状数组维护值域出现次数来统计。

因此做法是：

找最长严格递增后缀
先把这个后缀里的值加入树状数组
对每个前缀元素 $a[i]$ ，计算
$ans[i] = (start - i - 1) + sum(a[i])$
然后再把 $a[i]$ 加入树状数组

代码

cpp

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int a[MAXN];
int bit[MAXN];
int ans[MAXN];

int lowbit(int x) {
    return x & -x;
}

// 树状数组单点加一，表示某个数已经进入了“后缀有序段”。
void add(int pos, int val) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        bit[i] += val;
    }
}

// 查询当前已经放进去的数里，有多少个值 <= pos。
int sum(int pos) {
    int ret = 0;
    for (int i = pos; i > 0; i -= lowbit(i)) {
        ret += bit[i];
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int start = n;

    // 从后往前找最长严格递增后缀。
    while (start > 1 && a[start - 1] < a[start]) {
        start--;
    }

    cout << start - 1 << '\n';

    // 先把已经有序的后缀放入树状数组。
    for (int i = start; i <= n; i++) {
        add(a[i], 1);
    }

    for (int i = 1; i < start; i++) {
        // 把当前队首拿走后，前面还会保留 start-i-1 头“尚未处理”的奶牛。
        // 之后再接上已经有序的后缀里所有比它小的奶牛，这就是本次需要后移的步数。
        ans[i] = (start - i - 1) + sum(a[i]);
        add(a[i], 1);
    }

    if (start > 1) {
        for (int i = 1; i < start; i++) {
            if (i > 1) {
                cout << ' ';
            }
            cout << ans[i];
        }
    }
    cout << '\n';

    return 0;
}

复杂度

找后缀： $O(N)$
每次树状数组查询与修改： $O(log N)$

总时间复杂度：

$O(N log N)$

空间复杂度：

$O(N)$

总结

这题的难点不在树状数组本身，而在于先看出：

后缀里已经有一部分天然有序
只有前缀需要依次插入

树状数组只是把“有序集合里有多少个数比当前值小”这个统计，降成了 $O(log N)$ 。

[USACO19JAN] Sleepy Cow Sorting G

目录

题意

思路

代码

复杂度

总结