【洛谷-P1056】解题报告（模拟）

原始题目

P1056 排座椅

题目大意

给出一个\(M\)行\(N\)列的矩形，某些相邻的同学交头接耳，设置\(K\)条横向通道，\(L\)条纵向通道给出最好的划分方案，能避免最多组同学交头接耳。

解题思路

对每一行/列交头接耳的同学对数计数，分别对行列排序后排序输出前k或l个。（注意输出的时候按照字典序，所以要将前k或l个做二次排序，这里有些小坑）。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;

#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define fi first
#define se second

int m, n, a, b, d;
int xx1, yy1, xx2, yy2;

struct node {
    int id;
    int cnt;
};
node xx[maxn], yy[maxn];

bool cmp(node a, node b)
{
    return a.cnt > b.cnt;
}

bool cmp1(node a, node b)
{
    return a.id < b.id;
}

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> m >> n >> a >> b >> d) {
        rep(i, 1, m + 1) xx[i].id = i, xx[i].cnt = 0;
        rep(i, 1, n + 1) yy[i].id = i, yy[i].cnt = 0;
        rep(i, 0, d)
        {
            cin >> xx1 >> yy1 >> xx2 >> yy2;
            if (xx1 == xx2) {
                yy[min(yy1, yy2)].cnt++;
            } else {
                xx[min(xx1, xx2)].cnt++;
            }
        }
        sort(xx + 1, xx + m + 1, cmp);
        sort(yy + 1, yy + n + 1, cmp);
        sort(xx + 1, xx + a + 1, cmp1);
        sort(yy + 1, yy + b + 1, cmp1);
        cout << xx[1].id;
        rep(i, 2, a + 1) cout << " " << xx[i].id;
        cout << endl;
        cout << yy[1].id;
        rep(i, 2, b + 1) cout << " " << yy[i].id;
        cout << endl;
    }
}

收获与反思

因为需要二次排序那里一直Wa，注意审题啊，题目输出格式里明确指出了。