[NOIP2008-普及] 排座椅

题目描述

教室里同学坐在 $M$ 行 $N$ 列的座位上，相邻两行、两列之间各有一条可开通道的"缝"（行缝 $M-1$ 条、列缝 $N-1$ 条），通道隔开所有跨越该缝的相邻同学对。给定 $D$ 对会交头接耳的同学（每对前后或左右相邻），要在行方向恰好开 $K$ 条通道、列方向恰好开 $L$ 条，使仍在说话的对数最少（保证最优方案唯一），输出所选行缝、列缝编号（各升序）。

输入：第一行 5 个整数 $M,N,K,L,D$ （ $2 \le N,M \le 1000$ ）；接下来 $D$ 行每行 4 个整数 $X_i,Y_i,P_i,Q_i$ ，表示 $(X_i,Y_i)$ 与 $(P_i,Q_i)$ 会交头接耳。输出：两行，分别是 $K$ 个升序行缝编号和 $L$ 个升序列缝编号。样例：输入 4 5 1 2 3 及三对同学 (4,2)-(4,3)、(2,3)-(3,3)、(2,5)-(2,4)，输出 2 和 2 4。

思路

行缝只能隔开前后相邻的对、列缝只能隔开左右相邻的对，两组决策独立；且每对同学只跨一条缝，各缝贡献可单独统计、互不冲突。读入时给对应缝（编号取相邻坐标的较小值）计数加一，再各取计数最大的 $K$ 个行缝、 $L$ 个列缝升序输出，贪心由交换论证易证。

参考代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

rows: list[list[int]]  # rows[i] = i 与 i+1 行之间开通道能隔开的说话对数
cols: list[list[int]]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n, k, l, d = next(data), next(data), next(data), next(data), next(data)

    # 统计每个"行缝"（i 与 i+1 行之间）和"列缝"（j 与 j+1 列之间）各能隔开几对
    rows = [0] * m
    cols = [0] * n
    for _ in range(d):
        x, y, p, q = next(data), next(data), next(data), next(data)
        if x == p:
            cols[min(y, q)] += 1
        else:
            rows[min(x, p)] += 1

    # 各取隔开对数最多的 K / L 条缝：排序后取前 K（L）个下标再升序输出
    row_id = sorted(range(1, m), key=lambda i: -rows[i])[:k]
    col_id = sorted(range(1, n), key=lambda j: -cols[j])[:l]
    print(' '.join(map(str, sorted(row_id))))
    print(' '.join(map(str, sorted(col_id))))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:05
 * update_at: 2026-10-06 14:05
 */

#include <bits/stdc++.h>
typedef long long ll;

const int MAXN = 1005;

ll m, n, k, l, d;
int row_cnt[MAXN]; // row_cnt[i] = 第 i 行与 i+1 行之间开通道能隔开的说话对数
int col_cnt[MAXN]; // col_cnt[j] = 第 j 列与 j+1 列之间开通道能隔开的说话对数
int row_id[MAXN];  // 行缝编号，用于排序
int col_id[MAXN];  // 列缝编号，用于排序

// 比较函数：按隔开的对数从大到小排序
bool cmp_row(int a, int b) {
    return row_cnt[a] > row_cnt[b];
}
bool cmp_col(int a, int b) {
    return col_cnt[a] > col_cnt[b];
}

int main() {
    scanf("%lld %lld %lld %lld %lld", &m, &n, &k, &l, &d);
    for (int i = 1; i < m; i++) row_id[i] = i; // 行缝编号 1..m-1
    for (int j = 1; j < n; j++) col_id[j] = j; // 列缝编号 1..n-1

    // 每对说话同学：前后相邻给行缝计数，左右相邻给列缝计数，跨缝编号取较小坐标
    for (int i = 1; i <= d; i++) {
        ll x, y, p, q;
        scanf("%lld %lld %lld %lld", &x, &y, &p, &q);
        if (x == p)
            col_cnt[y < q ? y : q]++; // 左右相邻，隔开它的是列缝 min(y,q)
        else
            row_cnt[x < p ? x : p]++; // 前后相邻，隔开它的是行缝 min(x,p)
    }

    // 各取隔开对数最多的 K / L 条缝：按贡献排序取前 K（L）个下标
    std::sort(row_id + 1, row_id + m, cmp_row);
    std::sort(col_id + 1, col_id + n, cmp_col);

    // 选中的缝编号升序输出
    std::sort(row_id + 1, row_id + k + 1);
    std::sort(col_id + 1, col_id + l + 1);
    for (int i = 1; i <= k; i++) printf("%d%c", row_id[i], i == k ? '\n' : ' ');
    for (int j = 1; j <= l; j++) printf("%d%c", col_id[j], j == l ? '\n' : ' ');
    return 0;
}