[NOIP 2008 普及组] 排座椅

题意

教室里有 M 行 N 列座位，需要开：

K 条横向通道
L 条纵向通道

已知有 D 对同学会交头接耳，并且每对同学保证是上下相邻或左右相邻。

如果某条通道正好开在这两人中间，那么这对同学就会被隔开，不再交头接耳。

要求选择通道位置，使得最后还能交头接耳的同学对数最少。

思路

先看一个最直接的暴力：

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#include <bits/stdc++.h>
using namespace std;

const int MAXD = 1005;

struct Talk {
    int x1, y1, x2, y2;
};

int m, n, k, l, d;
Talk a[MAXD];
vector<int> choose_row, choose_col;
vector<int> best_row, best_col;
int best_blocked = -1;

// 判断某一对同学是否会被当前通道方案隔开。
bool is_blocked(const Talk &t) {
    if (t.x1 != t.x2) {
        int gap = min(t.x1, t.x2);
        for (int i = 0; i < (int) choose_row.size(); i++) {
            if (choose_row[i] == gap) {
                return true;
            }
        }
        return false;
    }
    else {
        int gap = min(t.y1, t.y2);
        for (int i = 0; i < (int) choose_col.size(); i++) {
            if (choose_col[i] == gap) {
                return true;
            }
        }
        return false;
    }
}

// 比较两个方案的字典序，便于在小数据对拍时固定输出。
bool better_lexicographically(const vector<int> &row1, const vector<int> &col1,
                              const vector<int> &row2, const vector<int> &col2) {
    if (row1 != row2) {
        return row1 < row2;
    }
    return col1 < col2;
}

void evaluate() {
    int blocked = 0;
    for (int i = 1; i <= d; i++) {
        if (is_blocked(a[i])) {
            blocked++;
        }
    }

    if (blocked > best_blocked ||
        (blocked == best_blocked &&
         better_lexicographically(choose_row, choose_col, best_row, best_col))) {
        best_blocked = blocked;
        best_row = choose_row;
        best_col = choose_col;
    }
}

void dfs_col(int pos, int need) {
    if (need == 0) {
        evaluate();
        return;
    }
    if (pos >= n) {
        return;
    }
    if (n - pos < need) {
        return;
    }

    choose_col.push_back(pos);
    dfs_col(pos + 1, need - 1);
    choose_col.pop_back();

    dfs_col(pos + 1, need);
}

void dfs_row(int pos, int need) {
    if (need == 0) {
        dfs_col(1, l);
        return;
    }
    if (pos >= m) {
        return;
    }
    if (m - pos < need) {
        return;
    }

    choose_row.push_back(pos);
    dfs_row(pos + 1, need - 1);
    choose_row.pop_back();

    dfs_row(pos + 1, need);
}

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

    cin >> m >> n >> k >> l >> d;
    for (int i = 1; i <= d; i++) {
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
    }

    dfs_row(1, k);

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

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

    return 0;
}

暴力做法就是：

枚举选哪 K 条横向缝
枚举选哪 L 条纵向缝
统计一共能隔开多少对同学

这个思路很直观，但显然不能用于大数据。

关键观察

每一对同学只会影响一条确定的缝：

如果他们上下相邻，只和某一条横向缝有关
如果他们左右相邻，只和某一条纵向缝有关

所以题目其实可以拆成两个彼此独立的问题：

在所有横向缝里选 K 条，让被隔开的上下相邻同学对数最多
在所有纵向缝里选 L 条，让被隔开的左右相邻同学对数最多

这张表可以把题目转成更直观的计数问题：

原题对象	统计含义
第 `i` 行和 `i+1` 行之间	一条横向缝
第 `j` 列和 `j+1` 列之间	一条纵向缝
一对上下相邻同学	给某条横向缝贡献 `1`
一对左右相邻同学	给某条纵向缝贡献 `1`

于是做法就很清楚了：

扫描所有 D 对同学
统计每条横向缝、纵向缝各自的贡献次数
分别按贡献从大到小排序
横向取前 K 条，纵向取前 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#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1005;

struct Node {
    int id;     // 这条缝的位置编号
    int cnt;    // 有多少对同学会被这条缝隔开
};

int m, n, k, l, d;
int row_cnt[MAXM], col_cnt[MAXM];
Node row_gap[MAXM], col_gap[MAXM];

bool cmp_node(const Node &a, const Node &b) {
    if (a.cnt != b.cnt) {
        return a.cnt > b.cnt;
    }
    return a.id < b.id;
}

bool cmp_int(int a, int b) {
    return a < b;
}

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

    cin >> m >> n >> k >> l >> d;

    for (int i = 1; i <= d; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 两人上下相邻，只会被某一条横向通道隔开。
        if (x1 != x2) {
            int gap = min(x1, x2);
            row_cnt[gap]++;
        }
        // 两人左右相邻，只会被某一条纵向通道隔开。
        else {
            int gap = min(y1, y2);
            col_cnt[gap]++;
        }
    }

    for (int i = 1; i < m; i++) {
        row_gap[i].id = i;
        row_gap[i].cnt = row_cnt[i];
    }
    for (int i = 1; i < n; i++) {
        col_gap[i].id = i;
        col_gap[i].cnt = col_cnt[i];
    }

    sort(row_gap + 1, row_gap + m, cmp_node);
    sort(col_gap + 1, col_gap + n, cmp_node);

    vector<int> ans_row, ans_col;
    for (int i = 1; i <= k; i++) {
        ans_row.push_back(row_gap[i].id);
    }
    for (int i = 1; i <= l; i++) {
        ans_col.push_back(col_gap[i].id);
    }

    sort(ans_row.begin(), ans_row.end(), cmp_int);
    sort(ans_col.begin(), ans_col.end(), cmp_int);

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

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

    return 0;
}

复杂度

时间复杂度： $O(D + M \log M + N \log N)$
空间复杂度： $O(M + N)$

总结

这题最重要的不是排序本身，而是先看出：

横向通道和纵向通道是可以完全拆开的
每一对同学只会对应一条唯一的缝

一旦把这个关系看清，题目就只剩下“计数 + 排序取前几名”。

[NOIP 2008 普及组] 排座椅

目录

题意

思路

关键观察

代码

复杂度

总结