排座椅

排座椅

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

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

题解:
贪心,因为你的行数和列数是一定得,所以每用一行或一列就需要尽量隔开尽量多得学生,所以我们首先需要统计,对于每一列来说,这一列有多少个说话得学生,然后按照人数进行排序,然后选取人数尽量多得列进行相隔,
行也如此。

再对选出来得进行由小到大排序(题目要求从小到大输出) 输出即可

代码:

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <string>
//#define int long long
const int maxn = 1e3+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9+7;
using namespace std;

struct node{
    int id,cnt;
};
node a[maxn],b[maxn];

void init(){
    for(int i=0;i<1001;i++){
        a[i].id=i;
        b[i].id=i;
    }
}
//行号 x  a
//列好 y  b
struct rule{
    bool operator () (const node & a,const node & b){
        return a.cnt>b.cnt;
    }
};

int main()
{
    int n,m,k,l,d;
    init();
    cin>>n>>m>>k>>l>>d;
    for(int i=0;i<d;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2){
            int pos=min(y1,y2);
            b[pos].cnt++;
        }
        else{
            int pos=min(x1,x2);
            a[pos].cnt++;
        }
    }
    sort(a,a+1000,rule());
    sort(b,b+1000,rule());
    vector<int> ans1,ans2;
    for(int i=0;i<k;i++)  ans1.push_back(a[i].id);
    for(int i=0;i<l;i++)  ans2.push_back(b[i].id);
    sort(ans1.begin(),ans1.end());
    sort(ans2.begin(),ans2.end());
    for(auto it : ans1){
        if(it==ans1.back()) cout<<it<<endl;
        else cout<<it<<" ";
    }
    for(auto it : ans2){
        if(it==ans2.back()) cout<<it<<endl;
        else cout<<it<<" ";
    }
    return 0;
}
题解 文章被收录于专栏

主要写一些题目的题解

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务