【每日一题】排座椅

题目

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

解题思路

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

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

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

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;
}