【NOIP普及】排座椅

---

题目描述

上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的 D 对同学上课时会交头接耳。
同学们在教室中坐成了 M 行 N 列，坐在第 ii 行第 jj 列的同学的位置是(i,j)，为了方便同学们进出，在教室中设置了KK 条横向的通道，L 条纵向的通道。
于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了 2 个会交头接耳的同学，那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

输入格式

第一行，有 5 个用空格隔开的整数，分别是M,N,K,L,D（2<=M,N<=1000,0<=K<M,0<=L<N,D<=2000）
接下来的D行，每行有 4个用空格隔开的整数。第 i行的 4 个整数$X_i,Y_i,P_i,Q_i$，表示坐在$(X_i,Y_i)与(P_i,Q_i)$的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。
输入数据保证最优方案的唯一性。

输出格式

样例输入

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

样例输出

2
2 4

解题思路

这道题就是让我们求在哪里划线可以隔开最多的两个值相等的数。
我们可以用贪心算法。
首先，查找每相邻两行有几对会交头接耳的，只要有，就用一个结构体保存下数量和当前所在的行。统计完后，按照数量从大到小排序。然后取出前k个数，再按照行的编号从小到大排序，输出即可。

Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#define sco 2000
using namespace std;
struct td{
	int number,hen;
}class2[sco],class1[sco];
int m,n,k,l,d,a[sco],b[sco];
bool cmp(td x1,td y1){
	return x1.number>y1.number;
}
int main(){
	freopen("seat.in","r",stdin);
	freopen("seat.out","w",stdout);
	scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
	for(int i=1;i<=n;++i)class1[i].hen=i;
	for(int i=1;i<=m;++i)class2[i].hen=i;
	for(int i=1;i<=d;++i){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x1==x2 and y1+1==y2){
			++class1[y1].number;
		}
		else if(x1==x2 and y2+1==y1){
			++class1[y2].number;
		}
		else if(x1+1==x2 and y1==y2){
			++class2[x1].number;
		}
		else if(x2+1==x1 and y1==y2){
			++class2[x2].number;
		}
	}
	sort(class1+1,class1+n+1,cmp);
	sort(class2+1,class2+1+m,cmp);
	for(int i=1;i<=k;++i){
		a[i]=class2[i].hen;
	}sort(a+1,a+1+k);
	for(int i=1;i<=k;++i){
		printf("%d ",a[i]);
	}
	if(k)printf("\n");
	for(int i=1;i<=l;++i){
		a[i]=class1[i].hen;
	}sort(a+1,a+l+1);
	for(int i=1;i<=l;++i){
		printf("%d ",a[i]);
	}
	return 0;
	fclose(stdin);
	fclose(stdout);
}

---

谢谢阅读