【问题描述】

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

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

【输入描述】

第一行，有55个用空格隔开的整数，分别是M,N,K,L,D（2≤N,M≤1000, 0≤K<M,0≤L<N,D≤2000）

接下来D行，每行有4个用空格隔开的整数。第i行的4个证书Xi，Yi，Pi，Oi表示坐在位置（Xi，Yi）与（Pi，Oi）的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。

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

【输出描述】

共两行。

第一行包含K个整数，a1,a2……ak表示第a1行和a1+1行之间、第a2行和第a2+1行之间、…、第aK行和第aK+1行之间要开辟通道，其中ai＜ai+1,每两个整数之间用空格隔开（行尾没有空格）。

第二行包含LL个整数，b1b2……bL，表示第b1列和b1+1列之间，第b2列和b2+1列之间、…、第bL列和第bL+1列之间要开辟通道，其中bi＜bi+1，每两个整数之间用空格隔开（行尾没有空格）。

【样例输入1】

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

【样例输出1】

2
2 4

【样例解释】

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

【题目分析】

1.先判断两个交头接耳的人中间的过道是横向还是纵向
2.要使方案最优，使用桶排序，记录两个交头接耳的人中需要设置哪条通道，被需要最多的通道一定要设置 
3.遍历桶排序中的所有值，找出最大值，把最大值的数值设为-1
4.输出数组中值为-1的下标 

【参考代码】

#include<bits/stdc++.h>
using namespace std;
int a[1005],b[1005];//创建数组 
int main()
{
	int m,n,k,l,d,x,y,p,q,max=-1,t;
	cin>>m>>n>>k>>l>>d;
	for(int i=1;i<=d;i++)
	{
		cin>>x>>y>>p>>q;
		if(abs(x-p)==1)
		{
			a[min(x,p)]++;//横向 
		} 
		if(abs(y-q)==1)
		{
			b[min(y,q)]++;//纵向 
		}
	} 
	for(int i=1;i<=k;i++)
	{
		max=-1;
		for(int j=1;j<=1000;j++)
		{
			if(a[j]>max)
			{
				max=a[j];//记录能分开多少对交头接耳的学生的最大值 
				t=j;//记录下标 
			}
		}
		a[t]=-1;//最多能分开的交头接耳的学生 
	}//横向 
	for(int i=1;i<=l;i++)
	{
		max=-1;
		for(int j=1;j<=1000;j++)
		{
			if(b[j]>max)
			{
				max=b[j];//记录能分开多少对交头接耳的学生的最大值 
				t=j;//记录下标 
			}
		}
		b[t]=-1;//最多能分开的交头接耳的学生 
	}//纵向 
	for(int i=1;i<=1000;i++)
	{
		if(a[i]==-1)
		{
			cout<<i<<" ";//输出横向的过道 
		}
	}
	cout<<endl;
	for(int i=1;i<=1000;i++)
	{
		if(b[i]==-1)
		{
			cout<<i<<" ";//输出纵向的过道 
		}
	}
	return 0;	
}