P1056 [NOIP 2008 普及组] 排座椅——题解

解题思路

每一对上下相邻学生只会被它们之间的横向通道隔开，因此给对应行间位置计数；左右相邻同理给列间位置计数。选择计数最大的 $K$ 个行间位置和最大的 $L$ 个列间位置即可。最后按位置升序输出。

复杂度分析

计数 $O(D)$，排序 $O(M\log M+N\log N)$，空间复杂度 $O(M+N)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
struct Node{int id,c;};
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int M,N,K,L,D;cin>>M>>N>>K>>L>>D;
    vector<int> r(M,0),c(N,0);
    for(int i=0;i<D;i++){
        int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
        if(x1==x2) c[min(y1,y2)]++;
        else r[min(x1,x2)]++;
    }
    vector<Node> vr,vc;
    for(int i=1;i<M;i++) vr.push_back({i,r[i]});
    for(int i=1;i<N;i++) vc.push_back({i,c[i]});
    auto cmp=[](const Node&a,const Node&b){return a.c!=b.c?a.c>b.c:a.id<b.id;};
    sort(vr.begin(),vr.end(),cmp);sort(vc.begin(),vc.end(),cmp);
    vector<int> ar,ac;
    for(int i=0;i<K;i++) ar.push_back(vr[i].id);
    for(int i=0;i<L;i++) ac.push_back(vc[i].id);
    sort(ar.begin(),ar.end());sort(ac.begin(),ac.end());
    for(int i=0;i<K;i++) cout<<ar[i]<<(i+1==K?'\n':' ');
    if(K==0) cout<<'\n';
    for(int i=0;i<L;i++) cout<<ac[i]<<(i+1==L?'\n':' ');
    if(L==0) cout<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; struct Node{int id,c;}; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int M,N,K,L,D;cin>>M>>N>>K>>L>>D; vector r(M,0),c(N,0); for(int i=0;i<D;i++){ int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2; if(x1x2) c[min(y1,y2)]++; else r[min(x1,x2)]++; } vector vr,vc; for(int i=1;i<M;i++) vr.push_back({i,r[i]}); for(int i=1;i<N;i++) vc.push_back({i,c[i]}); auto cmp=[](const Node&a,const Node&b){return a.c!=b.c?a.c>b.c:a.id<b.id;}; sort(vr.begin(),vr.end(),cmp);sort(vc.begin(),vc.end(),cmp); vector ar,ac; for(int i=0;i<K;i++) ar.push_back(vr[i].id); for(int i=0;i<L;i++) ac.push_back(vc[i].id); sort(ar.begin(),ar.end());sort(ac.begin(),ac.end()); for(int i=0;i<K;i++) cout<<ar[i]<<(i+1K?'\n':' '); if(K0) cout<<'\n'; for(int i=0;i<L;i++) cout<<ac[i]<<(i+1L?'\n':' '); if(L==0) cout<<'\n'; return 0; }