排座椅

算法：贪心

思路：优先选隔开说话人多的线，用pair来存每条线能需要分隔次数和位置，然后用sort按照分隔次数从大到小排序，输出即可

时间复杂度：

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2010;

typedef pair<int,int> PII;
PII row[N],col[N];  //first表示需要分隔次数，second表示分隔线位置
int ans[N];

bool cmp(PII x,PII y){
    return x.first>y.first;
}

int main(){
    int m,n,k,l,d,cnt;
    cin>>m>>n>>k>>l>>d;

    for (int i = 1; i <= n; i ++ ) row[i].second = i;
    for (int i = 1; i <= m; i ++ ) col[i].second = i;

    while(d--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2) col[min(y1,y2)].first ++;
        else row[min(x1,x2)].first ++;
    }

    sort(row+1,row+n+1,cmp);
    cnt=0;
    for(int i=1;i<=k;i++){
        ans[cnt++]=row[i].second;
    } 
    sort(ans,ans+k);
    for(int i=0;i<k;i++){
        cout<<ans[i]<<" ";
    } 
    cout<<endl;

    sort(col+1,col+m+1,cmp);
    cnt=0;
    for(int i=1;i<=l;i++){
        ans[cnt++]=col[i].second;
    } 
    sort(ans,ans+l);
    for(int i=0;i<l;i++){
        cout<<ans[i]<<" ";
    } 
    cout<<endl;

    return 0;
}