每日一题 排座椅 (贪心)

一.题意

二.题解

参考于：zzugzx

考虑每对交头接耳的同学是独立的
所以可以计算每行和每列能隔开多少交头接耳的同学
然后找前 k 大的行和前 l 大的列进行隔开
找的时候要写升序，所以用个 vector 存一下排个序

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

const int manx=1e5+5;
const int N=5e2+5;
const int mod=1e9+7;

ll x[manx],y[manx],z[manx];
vector<ll>ans;
bool cmp1(ll i,ll j){
    return x[i]>x[j];
}
bool cmp2(ll i,ll j){
    return y[i]>y[j];
}
int main(){
    ll n=read(),m=read(),k=read(),l=read(),d=read();
    for(int i=1;i<=d;i++){
        ll x1=read(),y1=read(),x2=read(),y2=read();
        if(x1==x2) y[min(y1,y2)]++;
        else x[min(x1,x2)]++;
    }
    for(int i=1;i<=n;i++) z[i]=i;
    sort(z+1,z+1+n,cmp1);
    for(int i=1;i<=k;i++) ans.pb(z[i]);
    sort(ans.begin(),ans.end());
    for(auto x: ans) cout<<x<<" ";
    cout<<endl;
    ans.clear();
    for(int i=1;i<=m;i++) z[i]=i;
    sort(z+1,z+1+m,cmp2);
    for(int i=1;i<=l;i++) ans.pb(z[i]);
    sort(ans.begin(),ans.end());
    for(auto x: ans) cout<<x<<" ";
    cout<<endl;
    return 0;
}