P1056-排座椅

题目描述

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

本文链接:https://hctra.cn/index.php/archives/317/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2019 年 10 月 17 日 09 : 56 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论

2 条评论

  1. 寒光博客

    洛谷的题么哈哈哈

    1. 六月丶
      @寒光博客

      嗯啊,还在普及区鬼混哈哈