题解 | 排座椅

本题使用了max_element函数，自定义的compare函数需要返回p1.second<p2.second，注意是小于而非大于！因为max_element是通过找到排序后队列的最后一个数字作为最大值，故需要升序排序。

#include <algorithm>
#include <iostream>
#include <set>
#include <map>
using namespace std;
bool compare(pair<int,int> p1,pair<int,int> p2){
    return p1.second<p2.second;                       //升序排序，最后一个元素最大。
}

int main(){
    int n,m,k,l,d,x1,y1,x2,y2;
    cin>>n>>m>>k>>l>>d;
    map<int,int> m_row;
    map<int,int> m_col;
    set<int> s_row;
    set<int> s_col;
    for(int i=0;i<d;i++){
        cin>>x1>>y1>>x2>>y2;
        if(x1==x2){
            y1=min(y1,y2);
            if(m_row.find(y1)==m_row.end()) m_row[y1]=1;
            else m_row[y1]++;
        }
        else{
            x1=min(x1,x2);
            if(m_col.find(x1)==m_col.end()) m_col[x1]=1;
            else m_col[x1]++;
        }
    }
    while(k--){
        auto i=max_element(m_col.begin(),m_col.end(),compare);
        s_col.insert(i->first);
        m_col.erase(i);
    }
    while(l--){
        auto i=max_element(m_row.begin(),m_row.end(),compare);
        s_row.insert(i->first);
        m_row.erase(i);
    }
    for(auto i:s_col) cout<<i<<' ';
    cout<<endl;
    for(auto i:s_row) cout<<i<<' ';
    return 0;
}