题目描述
上课的时候总会有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。不过,班主任小雪发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的D对同学上课时会交头接耳。
同学们在教室中坐成了M行N列,坐在第i行第j列的同学的位置是(i,j),为了方便同学们进出,在教室中设置了K条横向的通道,L条纵向的通道。
于是,聪明的小雪想到了一个办法,或许可以减少上课时学生交头接耳的问题:她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了2个会交头接耳的同学,那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序,给出最好的通道划分方案。在该方案下,上课时交头接耳的学生的对数最少。
输入格式
第一行,有5个用空格隔开的整数,分别是M,N,K,L,D(2<=N,M<=1000,0<=k<M,0<=L<N,D<=2000)
接下来的D行,每行有4个用空格隔开的整数。第i行的4个整数X,Y,P,Q,表示坐在位置(X,Y)与(P,Q)的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。
输入数据保证最优方案的唯一性。
输出格式
共两行。
第一行包含K个整数a1,a2,...ak,表示第a1行和a1+1行之间、第a2行和a2+1行之间、...、第ak行和第ak+1之间要开辟通道,其中ai<ai+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条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。
思路
这道题其实可以用贪心的做法,因为前后桌谈话和左右桌谈话互不影响,前后桌只能用行隔开,左右桌只能用列隔开,所以只要把有尽量多的交头接耳学生对的行和列隔开就是最优解。
大致解法:可以先算出每一行及每一列上交头接耳的学生对数,分别存入kRow[1005]和lRow[1005]中,这时下标就分别是代表这一行或列有多少对交头接耳的学生,然后对这两个数组分别进行降序排序(注意因为下标与人数是对应关系,所以不能用sort),因为规定设置K条横向和L条纵向,所以各取前K个、L个元素,把这些元素的下标存入ks、ls数组,再对这两个数组进行升序排序,这里C++可以用sort函数,最后输出结果即可。
源码
#include<iostream>
#include<algorithm>
using namespace std;
int kRow[1005];
int lRow[1005];
int main(){
int row,col,k,l,d; //行,列,横向,纵向,说话对数
int x1,y1,x2,y2;
int ks[1005],ls[1005],maxk,maxl;
cin >> row >> col >> k >> l >> d;
for(int i = 0;i < d;i++) {
cin >> x1 >> y1 >> x2 >> y2;
if(x1==x2){
lRow[min(y1,y2)]++;
}
else if(y1==y2){
kRow[min(x1,x2)]++;
}
}
for(int i = 0;i < k;i++){
maxk = 1;
for(int j = 1;j <= row;j++){
if(kRow[j]>kRow[maxk])maxk = j;
}
ks[i] = maxk;
kRow[maxk] = 0;
}
for(int i = 0;i < l;i++){ //这两个排序基本一致,可以做成函数
maxl = 1;
for(int j = 1;j <= col;j++){
if(lRow[j]>lRow[maxl])maxl = j;
}
ls[i] = maxl;
lRow[maxl] = 0;
}
sort(ks,ks+k);
sort(ls,ls+l);
for(int i = 0;i < k-1;i++)cout << ks[i] << " ";
cout << ks[k-1] << endl;
for(int i = 0;i < l-1;i++)cout << ls[i] << " ";
cout << ls[l-1] << endl;
return 0;
}