题解：P1056 [NOIP2008 普及组] 排座椅

Qfaiser · 2025-01-18 14:18:00 · 题解

solution

贪心和模拟。

要求上课时交头接耳的学生对数最少，转化成求通道能阻断的学生对数最多。

题目保证给出的 D 对同学都是左右或前后相邻，若左右相邻，需要在列上间隔，若前后相邻，需要在行上间隔。由此，我们可以统计出每行能阻断的对数，我们选出前 K 多的行，将这些行按从大到小输出，列是同理的。

通过记录。

code

#include <bits/stdc++.h>
using namespace std;
int n, m, k, l, d, K[1005], L[1005], ans[1005];
pair<int, int> a[1005];
void solve (int x, int b[], int num) {
    ans[0]=0;
    for (int i=1; i<=x; ++i)
        a[i]={b[i], i};
    sort(a+1, a+x+1);
    for (int i=x; i>=x-num+1; --i)
        ans[++ans[0]]=a[i].second;
    sort(ans+1, ans+num+1);
    for (int i=1; i<=num; ++i)
        cout << ans[i] << ' ';
}
int main () {
    cin >> n >> m >> k >> l >> d;
    for (int i=1, x, y, p, q; i<=d; ++i) 
        cin >> x >> y >> p >> q,
        x==p?L[min(y, q)]++:K[min(x, p)]++;
    solve(n, K, k);
    cout << '\n';
    solve(m, L, l);
    return 0;
}