P4810 排座椅（提高）

解题思路

1. 先想清楚：一对交头接耳的同学和通道是什么关系。 如果两个同学在同一行（X 相同），那么他们左右相邻，要在他们所在的两列之间开一条纵向通道；如果两个同学在同一列（Y 相同），那么他们上下相邻，要在他们所在的两行之间开一条横向通道。我们准备两个"计数器"：rowCount[i] 记"第 i 行和第 i+1 行之间"需要隔开的对数，colCount[j] 记"第 j 列和第 j+1 列之间"需要隔开的对数。
2. 读入 D 对同学并统计。 每读入一对位置 (X1,Y1) 和 (X2,Y2)，如果 X1==X2，说明左右相邻，通道应开在编号较小的一列那一侧，所以 colCount[min(Y1,Y2)] 加一；否则上下相邻，rowCount[min(X1,X2)] 加一。这样每一对同学都"登记"到它唯一依赖的那条通道上。
3. 贪心选择通道。 道理和"哪里人多就在哪里开过道"一样：一条通道能隔开越多的交头接耳对数，越应该优先开它。把所有横向通道（一共 M-1 条）按 rowCount 从大到小排序，取前 K 条；把纵向通道（一共 N-1 条）按 colCount 从大到小排序，取前 L 条。
4. 整理输出。 题目要求行号和列号都从小到大输出，所以把选出来的 K 个行号、L 个列号分别再排一次序，然后逐行逐列输出。题目保证最优方案唯一，所以即使有多条通道对数相同，也不会产生二义性。
5. 边界情况。 K 或 L 可能是 0，此时那一行输出为空行即可；M、N 最小是 2，数组下标都从 1 开始，不会越界。

参考代码

// 排座椅：统计每两条相邻行/列之间交头接耳的学生对数，贪心选择隔开对数最多的K行L列开通道
#include <iostream>
#include <algorithm>
using namespace std;

struct GapInfo {
    int count;   // 该条通道能隔开的交头接耳对数
    int index;   // 通道位置编号（第index行与第index+1行之间，或第index列与第index+1列之间）
};

// 比较函数：能隔开的对数多的通道排在前面；对数相同则编号小的在前
bool cmp(GapInfo a, GapInfo b) {
    if (a.count != b.count) return a.count > b.count;
    return a.index < b.index;
}

int rowCount[1005];   // rowCount[i] 记录第 i 行与第 i+1 行之间交头接耳的对数
int colCount[1005];   // colCount[j] 记录第 j 列与第 j+1 列之间交头接耳的对数

int main() {
    int M, N, K, L, D;
    cin >> M >> N >> K >> L >> D;
    for (int i = 0; i < D; i++) {
        int X1, Y1, X2, Y2;
        cin >> X1 >> Y1 >> X2 >> Y2;
        if (X1 == X2) {
            // 两个同学在同一行、左右相邻，通道开在他们所在的两列之间
            colCount[min(Y1, Y2)]++;
        } else {
            // 两个同学在同一列、上下相邻，通道开在他们所在的两行之间
            rowCount[min(X1, X2)]++;
        }
    }
    GapInfo rows[1005], cols[1005];
    int rowNum = 0, colNum = 0;
    for (int i = 1; i < M; i++) {   // 一共有 M-1 条横向通道可选
        rows[rowNum].count = rowCount[i];
        rows[rowNum].index = i;
        rowNum++;
    }
    for (int j = 1; j < N; j++) {   // 一共有 N-1 条纵向通道可选
        cols[colNum].count = colCount[j];
        cols[colNum].index = j;
        colNum++;
    }
    sort(rows, rows + rowNum, cmp);
    sort(cols, cols + colNum, cmp);
    // 挑选前 K 条横向通道、前 L 条纵向通道，并分别按编号从小到大排序输出
    int ansR[1005], ansC[1005];
    for (int i = 0; i < K; i++) ansR[i] = rows[i].index;
    for (int i = 0; i < L; i++) ansC[i] = cols[i].index;
    sort(ansR, ansR + K);
    sort(ansC, ansC + L);
    for (int i = 0; i < K; i++) {
        if (i > 0) cout << ' ';
        cout << ansR[i];
    }
    cout << endl;
    for (int i = 0; i < L; i++) {
        if (i > 0) cout << ' ';
        cout << ansC[i];
    }
    cout << endl;
    return 0;
}

复杂度分析

统计 D 对同学需要 O(D) 的时间；对 M-1 条横向通道和 N-1 条纵向通道排序分别是 O(M log M) 和 O(N log N)；最后对选出的 K、L 个编号再排序是 O(K log K + L log L)。题目中 M,N≤1000，D≤2000，这些操作加起来在一毫秒级，非常快。空间上只用了长度不超过 1005 的数组，是 O(M+N)。