题解 | #排座椅#

排座椅

https://ac.nowcoder.com/acm/problem/16618

链接：https://ac.nowcoder.com/acm/problem/16618
来源：牛客网

题号：NC16618
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 51200K，其他语言102400K
64bit IO Format: %lld

题目描述

上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。

同学们在教室中坐成了 MMM 行 NNN 列，坐在第 iii 行第 jjj 列的同学的位置是（i，j）（i，j）（i，j），为了方便同学们进出，在教室中设置了 KKK 条横向的通道，LLL 条纵向的通道。

于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。

请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。

输入描述:

第一行，有 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，每两个整数之间用空格隔开（行尾没有空格）。

示例1

输入

输出

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;
}