思路与算法

每对相邻学生只跨一条行或列边界，分别累计可隔开的对数，选最大K个行边界和L个列边界再升序输出。

正确性说明

一对相邻学生恰对应唯一边界，隔开总数是所选各边界计数之和。横纵通道独立、各边界贡献互不重叠，所以每类取最大的固定数量项达到最大隔开数，也即最小未隔开数。

复杂度

O(D+M log M+N log N)时间、O(M+N)空间，含计数数组清零。

易错点

源输入保证最优方案唯一；K或L为0仍输出对应空行，输出要按边界编号升序。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int m, n, k, l, d;
    cin >> m >> n >> k >> l >> d;
    vector<int> a(m), b(n);
    while (d--) {
        int x, y, p, q;
        cin >> x >> y >> p >> q;
        if (x != p)
            a[min(x, p)]++;
        else
            b[min(y, q)]++;
    }
    auto out = [](vector<int> a, int k) {
        vector<int> id(a.size() - 1);
        iota(id.begin(), id.end(), 1);
        sort(id.begin(), id.end(), [&](int x, int y) {
            return a[x] > a[y];
        });
        id.resize(k);
        sort(id.begin(), id.end());
        for (int i = 0; i < k; i++) {
            if (i)
                cout << ' ';
            cout << id[i];
        }
        cout << "\n";
    };
    out(a, k);
    out(b, l);
}