【问题描述】

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