【每日一题】排座椅

排座椅

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

题目

上课的时候总有一些同学和前后左右的人交头接耳。不过,班主任发现了一些有趣的现象,当同学们的座次确定下来之后,只有有限的 对同学上课时会交头接耳。
同学们在教室中坐成了 列,坐在第 行第 列的同学的位置是
为了方便同学们进出,在教室中设置了 条横向的通道, 条纵向的通道。
班主任为了减少上课时交头接耳的学生,她打算重新摆放桌椅,改变同学们桌椅间通道的位置,因为如果一条通道隔开了两个会交头接耳的同学,那么他们就不会交头接耳了。
请给出最好的通道划分方案。在该方案下,上课时交头接耳的学生对数最少。

解题思路

记录行 与行 之间交头接耳的学生的对数。

记录列 与列 之间交头接耳的学生的对数。

按照学生对数从大到小的顺序对 排序,选择前 个对数最多的行和前 个对数最多的列,记录、排序并打印。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(vector<int>& v1, vector<int>& v2){
    if(v1[1]==v2[1])
        return v1[0]<v2[0];
    return v1[1]>v2[1];
}

int main(){
    int M, N, K, L, D;
    cin >> M >> N >> K >> L >> D;
    vector<vector<int>> row(M, vector<int>(2,0));
    vector<vector<int>> col(N, vector<int>(2,0));
    for(int i=0; i<M; ++i)
        row[i][0] = i;
    for(int i=0; i<N; ++i)
        col[i][0] = i;

    int x, y, p, q;
    for(int i=0; i<D; ++i){
        cin >> x >> y >> p >> q;
        if(x==p){
            int c = min(y,q);
            ++col[c][1];
        }
        else if(y==q){
            int r = min(x,p);
            ++row[r][1];
        }
    }

    sort(row.begin(), row.end(), cmp);
    sort(col.begin(), col.end(), cmp);
    vector<int> R, C;
    for(int i=0; i<K; ++i)
        R.push_back(row[i][0]);
    for(int i=0; i<L; ++i)
        C.push_back(col[i][0]);

    sort(R.begin(), R.end());
    sort(C.begin(), C.end());
    for(int i=0; i<K; ++i){
        cout << R[i];
        if(i==K-1) cout << endl;
        else cout << " ";
    }
    for(int i=0; i<L; ++i){
        cout << C[i];
        if(i==L-1) cout << endl;
        else cout << " ";
    }
    return 0;
}
全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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