舞蹈课

题意

反复让技术差最小、平局最靠左的相邻异性出列，输出配对顺序。

思路

每轮都要找"差值最小且最左"的相邻异性对，直接扫描为什么不行？

队伍最多 $2\times10^5$ 人，最多删除 $\frac{n}{2}$ 对。每轮重新扫描全部相邻对找最小值是 $O(n)$ ，共 $O(n)$ 轮，总代价 $O(n^2)$ 必然超时。但注意：一次删除只会让队伍少两个人，受影响的相邻关系只有两条，绝大部分候选根本没变。

“局部只变一点，但要全局取最小”，什么结构各管一头？

全局取最小 → 堆：把所有相邻异性对以 (差值, 左编号, 右编号) 放进小根堆，堆顶天然是当前最优。相邻关系 → 双向链表：用前驱、后继数组维护每个编号当前的左右邻居。两个结构各司其职，这就是"堆 + 链表"的组合。

删掉一对后，会产生哪些新候选？

一对 (left, right) 出列后，新的相邻关系只可能出现在"原来 left 左边的人"和"原来 right 右边的人"之间，所以新候选最多一个，推入堆即可。其余邻对关系不变，之前已经全部在堆里。

堆里会残留已经失效的候选，怎么处理？

出列后某些老候选的编号已经消失，或两人已不再相邻。弹出堆顶时检查：两人都还存活，且 nxt[left] == right 仍然成立；不满足就丢弃，继续弹下一个。这个"懒删除"避免了从堆中删除任意元素的操作。

"平局取最左"需要特殊处理吗？

不需要。候选元组按字典序排序，差值相同时左编号小的自然在堆顶；输出时先输出较小编号即可。

最多能配出多少对？

每配一对各消耗一个 B、一个 G，所以总对数上限是 $\min(cnt_B, cnt_G)$ 。关键性质：只要队伍里同时还有 B 和 G，就必然存在相邻异性对——否则所有相邻的人都相同，整支队伍就是同一性别，矛盾。因此不管初始怎么排列（交错也好、聚堆也好），都能一直配到某一方归零，总对数恰好是 $\min(cnt_B, cnt_G)$ ，排列顺序只决定配对的先后，不决定总对数。

堆保存所有当前或历史候选 (差值,左编号,右编号)，元组顺序自动处理平局。前驱、后继数组模拟双向链表；删除一对后只可能新产生跨过这两人的一个邻对。

堆中旧候选不主动删除，弹出时检查两人是否仍存活且仍相邻，不合法就跳过。

Python 知识

bytearray 紧凑保存存活标志。
两个整数列表实现节点固定编号的双向链表。
heapq 元组第二字段为左编号，天然满足最左优先。

代码

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;

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

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

    // 最多只能配 min(B, G) 对，与排列顺序无关：
    // 只要两队都还有人，就必然存在相邻异性对，所以总能配到一方归零
    int cnt_b = 0, cnt_g = 0;
    for (char c : gender) {
        if (c == 'B') cnt_b++;
        else cnt_g++;
    }
    int max_pairs = min(cnt_b, cnt_g);

    // 双向链表：prev[i]/nxt[i] 记录当前队伍中 i 的左右邻居
    vector<int> prev(n), nxt(n);
    for (int i = 0; i < n; i++) {
        prev[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n - 1] = -1;

    vector<char> alive(n, 1);
    // (差值, 左编号, 右编号)：字典序让差值最小、平局最左的候选在堆顶
    using Candidate = tuple<int, int, int>;
    priority_queue<Candidate, vector<Candidate>, greater<Candidate>> heap;
    for (int i = 0; i + 1 < n; i++) {
        if (gender[i] != gender[i + 1]) {
            heap.emplace(abs(skill[i] - skill[i + 1]), i, i + 1);
        }
    }

    vector<pair<int, int>> answer;
    while (!heap.empty()) {
        auto [diff, left, right] = heap.top();
        heap.pop();
        // 懒删除：有人已出列，或已不再相邻，则跳过
        if (!alive[left] || !alive[right] || nxt[left] != right) {
            continue;
        }
        answer.emplace_back(left + 1, right + 1);
        if ((int)answer.size() == max_pairs) {
            break; // 已配满 min(B, G) 对，剩余全是同性，不可能再配
        }
        alive[left] = alive[right] = 0;
        // 删除后只剩可能新产生一个跨过两人的邻对
        int new_left = prev[left], new_right = nxt[right];
        if (new_left >= 0) nxt[new_left] = new_right;
        if (new_right >= 0) prev[new_right] = new_left;
        if (new_left >= 0 && new_right >= 0 && gender[new_left] != gender[new_right]) {
            heap.emplace(abs(skill[new_left] - skill[new_right]), new_left, new_right);
        }
    }

    cout << answer.size() << "\n";
    for (auto [a, b] : answer) {
        cout << a << " " << b << "\n";
    }

    return 0;
}

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
33import heapq
import sys


input = sys.stdin.buffer.readline
n = int(input())
gender = input().strip()
skill = list(map(int, input().split()))
previous = [i - 1 for i in range(n)]
following = [i + 1 for i in range(n)]
following[-1] = -1
alive = bytearray(b"\1" * n)
heap = [(abs(skill[i] - skill[i + 1]), i, i + 1)
        for i in range(n - 1) if gender[i] != gender[i + 1]]
heapq.heapify(heap)
answer = []

while heap:
    _, left, right = heapq.heappop(heap)
    if not alive[left] or not alive[right] or following[left] != right:
        continue
    answer.append((left + 1, right + 1))
    alive[left] = alive[right] = 0
    new_left, new_right = previous[left], following[right]
    if new_left >= 0:
        following[new_left] = new_right
    if new_right >= 0:
        previous[new_right] = new_left
    if new_left >= 0 and new_right >= 0 and gender[new_left] != gender[new_right]:
        heapq.heappush(heap, (abs(skill[new_left] - skill[new_right]), new_left, new_right))

print(len(answer))
print("\n".join(f"{left} {right}" for left, right in answer))

可删除堆解法（C++）

手写小根堆并用 pos 数组记录每个候选（按左端点）在堆中的下标；弹出后旧候选 (r, nxt[r]) 直接按 pos 定位删除，新候选 (nl, nr) 原地覆盖 (nl, l) 的位置，堆中始终只含有效候选，无需懒删除。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136#include <bits/stdc++.h>
using namespace std;

struct Cand {
    int diff, left, right;
    bool operator<(const Cand& o) const {
        if (diff != o.diff) return diff < o.diff;
        return left < o.left;
    }
};

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

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

    // 最多只能配 min(B, G) 对，与排列顺序无关：
    // 只要两队都还有人，就必然存在相邻异性对，所以总能配到一方归零
    int cnt_b = 0, cnt_g = 0;
    for (char c : gender) {
        if (c == 'B') cnt_b++;
        else cnt_g++;
    }
    int max_pairs = min(cnt_b, cnt_g);

    // 双向链表：当前队伍中每个编号的左右邻居
    vector<int> prev(n), nxt(n);
    for (int i = 0; i < n; i++) {
        prev[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n - 1] = -1;

    // 手写小根堆（1-based）；pos[i] = 以 i 为左端点的候选在堆中的下标，-1 表示不在堆中
    vector<Cand> heap(n + 1);
    vector<int> pos(n, -1);
    int size = 0;

    auto swap_pos = [&](int a, int b) {
        swap(heap[a], heap[b]);
        pos[heap[a].left] = a;
        pos[heap[b].left] = b;
    };
    auto up = [&](int p) {
        while (p > 1 && heap[p] < heap[p >> 1]) {
            swap_pos(p, p >> 1);
            p >>= 1;
        }
    };
    auto down = [&](int p) {
        while ((p << 1) <= size) {
            int best = p;
            int left_child = p << 1;
            if (heap[left_child] < heap[best]) best = left_child;
            int right_child = left_child + 1;
            if (right_child <= size && heap[right_child] < heap[best]) best = right_child;
            if (best == p) break;
            swap_pos(p, best);
            p = best;
        }
    };
    auto push = [&](int l, int r) {
        heap[++size] = {abs(skill[l] - skill[r]), l, r};
        pos[l] = size;
        up(size);
    };
    // 删除堆中下标 p 处的候选
    auto erase_at = [&](int p) {
        swap_pos(p, size);
        --size;
        pos[heap[size + 1].left] = -1; // heap[size+1] 就是要删除的候选
        if (p <= size) {
            down(p);
            up(p);
        }
    };
    auto pop_top = [&]() {
        pos[heap[1].left] = -1;
        swap_pos(1, size);
        --size;
        if (size >= 1) down(1);
    };

    for (int i = 0; i + 1 < n; i++) {
        if (gender[i] != gender[i + 1]) push(i, i + 1);
    }

    vector<pair<int, int>> answer;
    while (size > 0) {
        int l = heap[1].left, r = heap[1].right;
        answer.emplace_back(l + 1, r + 1);
        if ((int)answer.size() == max_pairs) {
            break; // 已配满 min(B, G) 对，剩余全是同性，不可能再配
        }
        pop_top();

        int nl = prev[l], nr = nxt[r];
        if (nl >= 0) nxt[nl] = nr;
        if (nr >= 0) prev[nr] = nl;

        // 旧候选 (r, nxt[r]) 失效，从堆中删除
        if (nr >= 0 && pos[r] != -1) {
            erase_at(pos[r]);
        }

        // 旧候选 (prev[l], l)：新候选 (nl, nr) 左端点相同，原地覆盖或删除
        if (nl >= 0 && pos[nl] != -1) {
            if (nr >= 0 && gender[nl] != gender[nr]) {
                int p = pos[nl];
                heap[p] = {abs(skill[nl] - skill[nr]), nl, nr};
                down(p);
                up(p);
            } else {
                erase_at(pos[nl]);
            }
        } else if (nl >= 0 && nr >= 0 && gender[nl] != gender[nr]) {
            // (nl, l) 是同性对从未入堆，新候选需要直接插入
            push(nl, nr);
        }
    }

    cout << answer.size() << "\n";
    for (auto [a, b] : answer) {
        cout << a << " " << b << "\n";
    }

    return 0;
}

复杂度

每人删除一次，每个新邻对入堆一次，时间 $O(n\log n)$ ，空间 $O(n)$ 。

总结

“动态相邻 + 全局最优”常用链表维护局部变化、堆维护全局候选，再以懒删除连接两者。

目录

题意

思路

Python 知识

代码

可删除堆解法（C++）

复杂度

总结