A8011.排座椅 题解

$\color{red}解题思路$：

$\color{blue}贪心策略$：让通道穿过尽可能多的交头接耳的同学对。

开两个结构体，存每行(列)的行(列)号和穿过的同学对数量。
每次输入 $X_i,Y_i,P_i,Q_i$ 就把他们中间那行(列)穿过的同学对数量加一。
再按照穿过同学对数量从大到小排序。
但最后别忘了按照行号(列号)从小到大排序。

---

#include <bits/stdc++.h>
using namespace std;
int m,n,k,l,d,x,y,p,q;
struct lin{
    int num,stu=0;
}a[1005];
struct col{
    int num,stu=0;
}b[1005];
bool cmp1(lin x,lin y){
    return x.stu>y.stu;
}
bool cmp2(col x,col y){
    return x.stu>y.stu;
}
bool cmp_1(lin x,lin y){
    return x.num<y.num;
}
bool cmp_2(col x,col y){
    return x.num<y.num;
}
int main(){
    cin>>n>>m>>k>>l>>d;
    for (int i=1;i<=d;i++){
        cin>>x>>y>>p>>q;
        if (y==q) a[min(x,p)].stu++;
        if (x==p) b[min(y,q)].stu++;
    }
    for (int i=1;i<=1000;i++){
        a[i].num=i;
        b[i].num=i;
    }
    sort(a+1,a+1001,cmp1);
    sort(b+1,b+1001,cmp2);
    sort(a+1,a+k+1,cmp_1);
    sort(b+1,b+l+1,cmp_2);
    for (int i=1;i<=k;i++) cout<<a[i].num<<' ';
    if (k) cout<<endl;
    for (int i=1;i<=l;i++) cout<<b[i].num<<' ';
    return 0;
}