题解 | 排座椅

// 其实贪心策略是一种贯穿生活的思想，而非一种算法

// 我们需要统计在哪个位置添加通道时，穿过的对子数量
// 然后按照升序对两个vector<pii>数组进行排序
// 最后输出前k个，和前l个

// 大宏大宏大宏

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n,m,k,l,d;cin>>n>>m>>k>>l>>d;
    unordered_map<int,int>mp1;      // 纵向
    unordered_map<int,int>mp2;      // 横向
    for (int i = 0;i < d;i++)
    {
        int a,b,c,e;cin>>a>>b>>c>>e;
        if (a == c)
        {
            int r = min(b,e);
            if (mp1.count(r) == 0)
                mp1[r] = 1;
            else  
                mp1[r]++;
        }
        if (b == e)
        {
            int r = min(a,c);
            if (mp2.count(r) == 0)
                mp2[r] = 1;
            else   
                mp2[r] ++;
        }
    }
    // 遍历哈希表装入vector容器
    // 排序找出前k个数字
    vector<pair<int,int>>v2;
    for (auto &p:mp2)
    {
        v2.emplace_back(p.second,p.first);
    }
    vector<pair<int,int>>v1;
    for (auto &p:mp1)
    {
        v1.emplace_back(p.second,p.first);
    }

    sort(v1.begin(),v1.end(),[](const pair<int,int>&a,const pair<int,int>&b){
        return a>b;
    });
    sort(v2.begin(),v2.end(),[](const pair<int,int>&a,const pair<int,int>&b){
        return a>b;
    });

    vector<int>res;
    for (int i = 0;i < k;i++)
    {
        res.push_back(v2[i].second);   
    }
    sort(res.begin(),res.end());
    for (int i:res)cout<<i<<' ';cout<<'\n';
    res.clear();

    for(int i = 0;i < l;i++) 
        res.push_back(v1[i].second);
    sort(res.begin(),res.end());
    for (int i:res)cout<<i<<' ';
}
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}
// 64 位输出请用 printf("%lld")