题解 | 排座椅

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

// 定义结构体pa，用于存储每一组交头接耳的两个相邻位置坐标
struct pa{
    ll x;  // 第一个位置的行号
    ll y;  // 第一个位置的列号
    ll p;  // 第二个位置的行号
    ll q;  // 第二个位置的列号
};

// 定义PII类型，first存储间隔的交头接耳次数，second存储间隔的编号
using PII=pair<ll,ll>;
const ll N=2e3+5;
pa a[N];          // 存储d组交头接耳的位置数据
PII al[1005];     // al[j]存储第j个列间隔的(次数, 编号)
PII ak[1005];     // ak[i]存储第i个行间隔的(次数, 编号)

int main() {
    // n：教室的行数，m：教室的列数，k：需要选择的行间隔数量
    // l：需要选择的列间隔数量，d：交头接耳的总对数
    ll n,m,k,l,d;
    cin>>n>>m>>k>>l>>d;
    ll cntk=0;     // 记录已选择的行间隔数量
    ll cntl=0;     // 记录已选择的列间隔数量

    // 步骤1：遍历所有交头接耳对，统计每个行/列间隔的交头接耳次数
    for(ll i=1;i<=d;i++){
        // 输入一组交头接耳的两个相邻位置坐标
        cin>>a[i].x>>a[i].y>>a[i].p>>a[i].q;
        
        // 情况1：x==p，说明是同一行左右相邻，对应列间隔
        if(a[i].x==a[i].p){
            // 若该列间隔还未初始化编号，则赋值间隔编号
            if(!al[min(a[i].y,a[i].q)].first){
                al[min(a[i].y,a[i].q)].second=min(a[i].y,a[i].q);
            }
            // 该列间隔的交头接耳次数加1
            al[min(a[i].y,a[i].q)].first++;
        }
        // 情况2：y==q，说明是同一列上下相邻，对应行间隔
        else if(a[i].y==a[i].q){
            // 若该行间隔还未初始化编号，则赋值间隔编号
            if(!ak[min(a[i].x,a[i].p)].first){
                ak[min(a[i].x,a[i].p)].second=min(a[i].x,a[i].p);
            }
            // 该行间隔的交头接耳次数加1
            ak[min(a[i].x,a[i].p)].first++;
        }
    }

    // 步骤2：对行间隔数组按「次数降序、编号升序」排序，优先选次数多的间隔
    sort(ak + 1, ak + n, [](PII a, PII b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    // 步骤3：对列间隔数组按「次数降序、编号升序」排序
    sort(al + 1, al + m, [](PII a, PII b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });

    // 步骤4：收集前k个行间隔和前l个列间隔的编号
    vector<ll>resk,resl;
    for(ll i=1;i<=n;i++){
        if(cntk==k)break;    // 选够k个行间隔则停止
        resk.push_back(ak[i].second); // 记录选中的行间隔编号
        cntk++;
    }
    for(ll i=1;i<=m;i++){
       if(cntl==l)break;     // 选够l个列间隔则停止
        resl.push_back(al[i].second); // 记录选中的列间隔编号
        cntl++;
    }

    // 步骤5：将选中的间隔编号按升序排序，满足题目输出顺序要求
    sort(resk.begin(),resk.end());
    sort(resl.begin(),resl.end());

    // 步骤6：输出排序后的行间隔编号
    for(auto t:resk){
        cout<<t<<" ";
    }
    cout<<endl;
    // 步骤7：输出排序后的列间隔编号
    for(auto t:resl){
        cout<<t<<" ";
    }
    return 0;
}