题解 | #排座椅#

分析

不难发现, 因为交头接耳的同学都是相邻的, 因此或者是相等的

另一个维度的最小值就是需要放置道路覆盖的位置

又因为每一对的交头接耳的同学只会影响一行或者一列

因此可以行列分开计算, 计算交头接耳同学前多的行和前多的列, 贪心即可

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

int n, m;
int k, l, d;

struct F {
    int cnt;
    int id;
    bool operator< (const F &f) const {
        return cnt > f.cnt;
    }
} a[N], b[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> k >> l >> d;
    for (int i = 1; i <= n; ++i) a[i].id = i;
    for (int i = 1; i <= m; ++i) b[i].id = i;

    for (int i = 0; i < d; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) {
            int y = min(y1, y2);
            b[y].cnt++;
        }
        else {
            int x = min(x1, x2);
            a[x].cnt++;
        }
    }

    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);

    vector<int> ans1, ans2;
    for (int i = 1; i <= min(k, n); ++i) ans1.push_back(a[i].id);
    for (int i = 1; i <= min(l, m); ++i) ans2.push_back(b[i].id);

    sort(ans1.begin(), ans1.end());
    sort(ans2.begin(), ans2.end());

    for (int i : ans1) cout << i << ' ';
    cout << '\n';
    for (int i : ans2) cout << i << ' ';
    cout << '\n';

    return 0;
}