排座椅（小白版）

题目链接

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

题目分析

在M行N列中，选K个行通道，L个列通道。这些通道能够分隔若干交头接耳的同学，让题目不再交头接耳。问怎么选取通道能让交头接耳的同学对数变少。

解题思路

交头接耳的同学位置是有特点的：不是纵向相邻就是横向相邻。这就意味着，行通道分隔的是纵向相邻的同学，也就是分隔的是列坐标相等的同学；列通道分隔的是横向相邻的同学，也就是分隔的是行坐标相等的同学。由此可见，对于横向相邻的同学和纵向相邻的同学，我们可以独立的分开计算，也就是行通道的最优选法和列通道的最优选法是可以分开求出且互相没有影响的。
所以求出能分隔最多纵向相邻的同学的K条行通道，求出能分隔最多横向相邻的同学的L条列通道就是最终答案。
算法：贪心

实现过程

step1：建立结构体数组lineh，结构体数组linel，分别表示行分隔线，列分隔线。
step2：按照每条线分隔同学对数由大到小排序。
step3：按照分隔线的序号（位置）从小到大排序，并输出。

代码解释

~~我起变量名比较随便~~
line[i].num代表编号为i的（行/列）分隔线分隔同学的对数；
line[i].num代表编号为i的（行/列）分隔线的编号。（这里可能比较难理解，主要是我的想法太鸡肋，往后看看应该能明白）
cmp_greater_less函数，用于sort，按照分隔线分隔同学的对数从大到小排序。
cmp函数，用于sort，按照分隔线编号从小到大排序。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
struct line{
    int num,id;
};
line lineh[N],linel[N];
bool cmp_greater_less(line a,line b){
    return a.num>b.num;
}
bool cmp(line a,line b){
    return a.id<b.id;
}
int main(){
    int m,n,k,l,d;
    int h1,h2,l1,l2;
    cin>>m>>n>>k>>l>>d;
    for(int i=1;i<=d;i++){
        cin>>h1>>l1>>h2>>l2;
        if(h1==h2) {int p=min(l1,l2);linel[p].num++;linel[p].id=p;}
        //p用来暂存（行）通道编号
        if(l1==l2) {int q=min(h1,h2);lineh[q].num++;lineh[q].id=q;}    
    }
    sort(lineh+1,lineh+1+m,cmp_greater_less);
    //按照分隔线分隔同学的对数从大到小排序，这里是把全部（行）通道进行了排序
    sort(lineh+1,lineh+1+k,cmp);
    //按照分隔线编号从小到大排序，这里是把k个被选出的（行）通道的编号进行了排序
    sort(linel+1,linel+1+n,cmp_greater_less);
    sort(linel+1,linel+1+l,cmp);
    for(int i=1;i<=k;i++) cout<<lineh[i].id<<' ';
    //其实这里要求最后无空格可以偷懒的
    cout<<endl;
    for(int i=1;i<=l;i++) cout<<linel[i].id<<' ';        
}

哔哔赖赖

我吐了，又是简单题没做出来，思路完全没问题，就是代码实现的时候，开始把行列坐标和横纵坐标搞混了居然认为样例错了（希望大家没有犯这个低级错误），改正这个小问题后，又一直把分隔线编号的排序按照所有分隔线进行了全排，应该排的是被选出的k个。就一直debug de不出来，最后疯了，也没能AC。
最后的最后，我想问上天一句：我什么时候才能成为大佬啊啊啊！！！