[noip2016-提高] 组合数问题

形式化题目

有 $n$ 条初始长度已知的蚯蚓，和一个常数 $q$ （每次切分后，除了切分出的两条新蚯蚓，其余所有蚯蚓长度都增加 $q$ ）。你一共需要切分 $m$ 次，每次从当前所有的蚯蚓中选出最长的一条，将其切成两段。设切分前该蚯蚓长度为 $x$ ，常数为 $u, v$ ，切分后的两段长度分别为 $\lfloor x \times \frac{u}{v} \rfloor$ 和 $x - \lfloor x \times \frac{u}{v} \rfloor$ 。要求输出两行信息：

每 $t$ 秒切断的蚯蚓在切断前的长度（以空格隔开）。
在所有切分完成后，每隔 $t$ 个输出剩余蚯蚓的长度，按照长度从大到小排列。

数据范围： $1 \le n \le 10^5, 0 \le m \le 7 \times 10^6, 0 < u < v \le 10^9, 0 \le q \le 200, 1 \le t \le 71$ 。

注意： 本题在原始题库中编号 3641，题面虽为「组合数问题」，但实际判题数据与格式完全对应的是 NOIP 2016 提高组的「蚯蚓」一题（首行形如 n m q u v t，且 .ans 存在大段多行序列且附有前导换行符等）。本题解已根据实际测试数据更正题意并提供匹配的算法。

正解

思路

每次要找出当前最长的蚯蚓切断，最直观的做法是使用优先队列维护当前所有蚯蚓的长度。由于每次除了被切断的蚯蚓外，其余所有蚯蚓都要增长 $q$ ，我们不需要对优先队列中的每一个元素进行修改，而是可以维护一个全局增加量 offset。每秒 offset += q，当切断一条原长度为 $L$ （通过队列最大值加上 offset 算出）的蚯蚓后，切出的两段长度计算出后要放入优先队列，为了抵消 offset，放入队列的值应减去当前的 offset + q。这种做法时间复杂度为 $O(m \log (n + m))$ 。然而，在本题中 $m$ 的范围高达 $7 \times 10^6$ ，优先队列的常数以及对数因子会超时。

注意到本题存在一个关键的单调性质： 若较早被切断的蚯蚓原长为 $x_1$ ，较晚被切断的蚯蚓原长为 $x_2$ ，则必然有 $x_1 \ge x_2$ 。 因此，对于长度更大的 $x_1$ ，其按固定比例 $\frac{u}{v}$ 切分出的两段长度 $\lfloor x_1 \frac{u}{v} \rfloor$ 和 $x_1 - \lfloor x_1 \frac{u}{v} \rfloor$ 在相同的增长时间下，必然也大于等于 $x_2$ 切分出的对应部分（考虑到 $x_2$ 虽多增长了，但在其被切的时候也仅仅是因为 $x_1$ 先被切掉）。也就是说，如果我们把新切出来的蚯蚓段放到单独的队列中，它们天然是按从大到小有序的。

因此，我们可以维护三个普通的队列：

队列 0：存放一开始就有的 $n$ 条蚯蚓，初始时将其降序排序。
队列 1：存放每次被切断后产生的第一条较短或按比例的那条蚯蚓段。
队列 2：存放每次被切断后产生的另一半蚯蚓段。

由于这三个队列内部都是单调递减的，每次选取当前最长的蚯蚓时，只需在这三个队列的队首比较大小，选取最大值即可，这样选取最大值的操作是 $O(1)$ 的。这类似于归并排序的过程。总时间复杂度被优化至 $O(n \log n + m)$ 。

代码

python

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    if len(input_data) < 6:
        return

    n = int(input_data[0])
    m = int(input_data[1])
    q = int(input_data[2])
    u = int(input_data[3])
    v = int(input_data[4])
    t = int(input_data[5])

    q0_arr = []
    for i in range(n):
        q0_arr.append(int(input_data[6 + i]))
    q0_arr.sort(reverse=True)

    head0 = 0
    tail0 = n

    from collections import deque
    q1 = deque()
    q2 = deque()

    offset = 0
    out1 = []

    for i in range(1, m + 1):
        max_val = -3000000000
        which = -1

        if head0 < tail0 and q0_arr[head0] > max_val:
            max_val = q0_arr[head0]
            which = 0
        if q1 and q1[0] > max_val:
            max_val = q1[0]
            which = 1
        if q2 and q2[0] > max_val:
            max_val = q2[0]
            which = 2

        if which == 0:
            head0 += 1
        elif which == 1:
            q1.popleft()
        elif which == 2:
            q2.popleft()

        L = max_val + offset

        if i % t == 0:
            out1.append(str(L))

        L1 = L * u // v
        L2 = L - L1

        q1.append(L1 - offset - q)
        q2.append(L2 - offset - q)

        offset += q

    if out1:
        sys.stdout.write(" ".join(out1) + "\n")
    else:
        sys.stdout.write("\n")

    out2 = []
    count = 0

    while head0 < tail0 or q1 or q2:
        max_val = -3000000000
        which = -1

        if head0 < tail0 and q0_arr[head0] > max_val:
            max_val = q0_arr[head0]
            which = 0
        if q1 and q1[0] > max_val:
            max_val = q1[0]
            which = 1
        if q2 and q2[0] > max_val:
            max_val = q2[0]
            which = 2

        if which == 0:
            head0 += 1
        elif which == 1:
            q1.popleft()
        elif which == 2:
            q2.popleft()

        count += 1
        if count % t == 0:
            out2.append(str(max_val + offset))

    if out2:
        sys.stdout.write(" ".join(out2) + "\n")
    else:
        sys.stdout.write("\n")


if __name__ == '__main__':
    solve()

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int MAXN = 100005;

int q0_arr[MAXN];

bool compare_desc(int a, int b) {
    return a > b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q, u, v, t;
    if (!(cin >> n >> m >> q >> u >> v >> t)) return 0;

    for (int i = 0; i < n; ++i) {
        cin >> q0_arr[i];
    }
    sort(q0_arr, q0_arr + n, compare_desc);

    int head0 = 0, tail0 = n;
    queue<int> q1, q2;

    long long offset = 0;
    bool first1 = true;

    for (int i = 1; i <= m; ++i) {
        long long max_val = -3000000000LL;
        int which = -1;

        if (head0 < tail0 && q0_arr[head0] > max_val) {
            max_val = q0_arr[head0];
            which = 0;
        }
        if (!q1.empty() && q1.front() > max_val) {
            max_val = q1.front();
            which = 1;
        }
        if (!q2.empty() && q2.front() > max_val) {
            max_val = q2.front();
            which = 2;
        }

        if (which == 0) head0++;
        else if (which == 1) q1.pop();
        else if (which == 2) q2.pop();

        long long L = max_val + offset;

        if (i % t == 0) {
            if (!first1) cout << " ";
            cout << L;
            first1 = false;
        }

        long long L1 = L * u / v;
        long long L2 = L - L1;

        q1.push((int)(L1 - offset - q));
        q2.push((int)(L2 - offset - q));

        offset += q;
    }
    cout << "\n";

    int count = 0;
    bool first2 = true;

    while (head0 < tail0 || !q1.empty() || !q2.empty()) {
        long long max_val = -3000000000LL;
        int which = -1;

        if (head0 < tail0 && q0_arr[head0] > max_val) {
            max_val = q0_arr[head0];
            which = 0;
        }
        if (!q1.empty() && q1.front() > max_val) {
            max_val = q1.front();
            which = 1;
        }
        if (!q2.empty() && q2.front() > max_val) {
            max_val = q2.front();
            which = 2;
        }

        if (which == 0) head0++;
        else if (which == 1) q1.pop();
        else if (which == 2) q2.pop();

        count++;
        if (count % t == 0) {
            if (!first2) cout << " ";
            cout << (max_val + offset);
            first2 = false;
        }
    }
    cout << "\n";

    return 0;
}

复杂度

时间复杂度：初始时对给定的 $n$ 条蚯蚓排序，花费 $O(n \log n)$ 。随后进行 $m$ 次切分，每次只需要比较三个队列的队首，选取最大值并进行相应的进队出队操作，花费 $O(m)$ 。最后把三个队列剩余元素取空输出，花费 $O(n + m)$ 。总时间复杂度为 $O(n \log n + m)$ 。
空间复杂度：需要开三个数组模拟队列。队列 0 需要 $O(n)$ ，队列 1 和队列 2 各自最多需要 $O(m)$ ，所以总空间复杂度为 $O(n + m)$ ，完全满足本题要求。

总结

利用隐藏的单调性，将需要 $O(\log n)$ 维护最值的优先队列退化成了三个相互之间有单调性的普通队列，将复杂度成功优化至线性的 $O(n \log n + m)$ 。这是处理这类题目的极其经典的技巧。
对于全局所有元素的集体变化，应采用偏移量（offset）进行相对管理，极大程度提升了效率。
数据排坑提示：本题题库中的题面描述是「组合数问题」，但实际判题系统挂载的测试数据完全是「蚯蚓」一题（即六个参数输入 n m q u v t 等特征）。本题必须以数据特征为准。部分答案文件带有前导空行等均属于数据固有特征。

[noip2016-提高] 组合数问题

目录

形式化题目

正解

思路

代码

复杂度

总结