题解 | #排座椅#

排座椅

https://ac.nowcoder.com/acm/problem/16618

链接:https://ac.nowcoder.com/acm/problem/16618
来源:牛客网
题号:NC16618
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 51200K,其他语言102400K
64bit IO Format: %lld

题目描述

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

输入描述:

第一行,有 5 各用空格隔开的整数,分别是 M,N,K,L,D(2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000)M,N,K,L,D(2 ≤ N,M ≤ 1000,0 ≤ K < M,0 ≤ L < N,D ≤ 2000)MNKLD2NM10000K<M0L<ND2000。
接下来 DDD 行,每行有 4 个用空格隔开的整数,第 iii 行的 4 个整数 Xi,Yi,Pi,QiX_i,Y_i,P_i,Q_iXiYiPiQi,表示坐在位置 (Xi,Yi)(X_i,Y_i)(Xi,Yi)(Pi,Qi)(P_i,Q_i)(Pi,Qi) 的两个同学会交头接耳(输入保证他们前后相邻或者左右相邻)。
	
输入数据保证最优方案的唯一性。

输出描述:

	
共两行
第一行包含 KKK 个整数,a1a2……aKa_1a_2……a_Ka1a2aK,表示第 a1a_1a1 行和 a1+1a_1+1a1+1 行之间、第 a2a_2a2 行和第 a2+1a_2+1a2+1 行之间、…、第 aKa_KaK 行和第 aK+1a_K+1aK+1 行之间要开辟通道,其中 ai<ai+1a_i < a_{i+1}ai<ai+1,每两个整数之间用空格隔开(行尾没有空格)。 第二行包含 LLL 个整数,b1b2……bkb_1b_2……b_kb1b2bk,表示第 b1b_1b1 列和 b1+1b_1+1b1+1 列之间、第 b2b_2b2 列和第 b2+1b_2+1b2+1 列之间、…、第 bLb_LbL 列和第 bL+1b_L+1bL+1 列之间要开辟通道,其中 bi<bi+1b_i< b_{i+1}bi<bi+1,每两个整数之间用空格隔开(行尾没有空格)。
示例1

输入

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

输出

2
2 4

说明

	
上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置,图中3条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。
本题从一条横轴和一条竖轴上说话学生多少入手求解,一条线上说话学生越多的肯定是要先隔开,统计各个坐标轴上的数量然后进行一个排序即可。这道题坑的一个小点在于最后的结果要根据坐标从小到大排序,这时候就不能是单纯的散列了,需要使用一个结构体来保存原来的坐标才行。
代码:
#include <bits/stdc++.h>


using namespace std;
struct Node {
    int pos = INT_MAX;
    int sum = 0;
};
const int MAXN = 10006;
int M,N,K,L,D;
Node x_pos[MAXN];
Node y_pos[MAXN];
int x_n = 0;
int y_n = 0;

bool comp(Node n, Node m) {
    if (n.sum>m.sum) return true;
    else return false;
}

bool comp2(Node n, Node m) {
    return n.pos<m.pos;
}

int main() {
    cin>>M>>N>>K>>L>>D;
    int x, y, p, q;
    for (int i=0;i<D;i++) {
        cin>>x>>y>>p>>q;
        if (x!=p) {
            if (x>p) {x_pos[p].sum++;x_pos[p].pos=p;}
            else {x_pos[x].sum++;x_pos[x].pos = x;}
        }
        if (y!=q) {
            if (y>q) {y_pos[q].sum++;y_pos[q].pos=q;}
            else {y_pos[y].sum++;y_pos[y].pos = y;}
        }
    }
    sort(x_pos, x_pos+MAXN,comp);
    sort(x_pos, x_pos+K,comp2);
    sort(y_pos, y_pos+MAXN,comp);
    sort(y_pos, y_pos+L,comp2);
    int xn = 0;
    int yn = 0;
    bool flag = true;
    while (K) {
        if (flag) {
            cout<<x_pos[xn].pos;
        } else cout<<" "<<x_pos[xn].pos;
        flag = false;
        xn++;
        K--;
    }
    flag = true;
    cout<<endl;
    while (L) {
        if (flag) {
            cout<<y_pos[yn].pos;
        } else cout<<" "<<y_pos[yn].pos;
        flag = false;
        
        yn++;
        L--;
    }
    return 0;
}
全部评论

相关推荐

Gaynes:查看图片
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务