题解 | #排座椅#

输入描述:

第一行，有 5 各用空格隔开的整数，分别是 M，N，K，L，D（2≤N，M≤1000，0≤K<M，0≤L<N，D≤2000）M，N，K，L，D（2 ≤ N，M ≤ 1000，0 ≤ K < M，0 ≤ L < N，D ≤ 2000）M，N，K，L，D（2≤N，M≤1000，0≤K<M，0≤L<N，D≤2000）。
接下来 DDD 行，每行有 4 个用空格隔开的整数，第 iii 行的 4 个整数 Xi，Yi，Pi，QiX_i，Y_i，P_i，Q_iXi，Yi，Pi，Qi，表示坐在位置 (Xi,Yi)(X_i,Y_i)(Xi,Yi) 与 (Pi,Qi)(P_i,Q_i)(Pi,Qi) 的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。
	

		输入数据保证最优方案的唯一性。
	

输出描述:

	

		共两行
	

	

		第一行包含 KKK 个整数，a1a2……aKa_1a_2……a_Ka1a2……aK，表示第 a1a_1a1 行和 a1+1a_1+1a1+1 行之间、第 a2a_2a2 行和第 a2+1a_2+1a2+1 行之间、…、第 aKa_KaK 行和第 aK+1a_K+1aK+1 行之间要开辟通道，其中 ai<ai+1a_i < a_{i+1}ai<ai+1，每两个整数之间用空格隔开（行尾没有空格）。
第二行包含 LLL 个整数，b1b2……bkb_1b_2……b_kb1b2……bk，表示第 b1b_1b1 列和 b1+1b_1+1b1+1 列之间、第 b2b_2b2 列和第 b2+1b_2+1b2+1 列之间、…、第 bLb_LbL 列和第 bL+1b_L+1bL+1 列之间要开辟通道，其中 bi<bi+1b_i< b_{i+1}bi<bi+1，每两个整数之间用空格隔开（行尾没有空格）。
	

4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

2
2 4

	

		
	

	

		上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。
	

#include <bits/stdc++.h>


using namespace std;
struct Node {
    int pos = INT_MAX;
    int sum = 0;
};
const int MAXN = 10006;
int M,N,K,L,D;
Node x_pos[MAXN];
Node y_pos[MAXN];
int x_n = 0;
int y_n = 0;

bool comp(Node n, Node m) {
    if (n.sum>m.sum) return true;
    else return false;
}

bool comp2(Node n, Node m) {
    return n.pos<m.pos;
}

int main() {
    cin>>M>>N>>K>>L>>D;
    int x, y, p, q;
    for (int i=0;i<D;i++) {
        cin>>x>>y>>p>>q;
        if (x!=p) {
            if (x>p) {x_pos[p].sum++;x_pos[p].pos=p;}
            else {x_pos[x].sum++;x_pos[x].pos = x;}
        }
        if (y!=q) {
            if (y>q) {y_pos[q].sum++;y_pos[q].pos=q;}
            else {y_pos[y].sum++;y_pos[y].pos = y;}
        }
    }
    sort(x_pos, x_pos+MAXN,comp);
    sort(x_pos, x_pos+K,comp2);
    sort(y_pos, y_pos+MAXN,comp);
    sort(y_pos, y_pos+L,comp2);
    int xn = 0;
    int yn = 0;
    bool flag = true;
    while (K) {
        if (flag) {
            cout<<x_pos[xn].pos;
        } else cout<<" "<<x_pos[xn].pos;
        flag = false;
        xn++;
        K--;
    }
    flag = true;
    cout<<endl;
    while (L) {
        if (flag) {
            cout<<y_pos[yn].pos;
        } else cout<<" "<<y_pos[yn].pos;
        flag = false;
        
        yn++;
        L--;
    }
    return 0;
}