题解 | #排座椅#

这道题的思路是贪心，为什么是贪心呢，因为能划分的行、列过道都是有限个数，要是想在有限个数里面选取最优解，那显然是找同一个两行里面交头接耳人数最多的两行中间加过道，列也是如此。

不过这里有坑点，就是他要求输出时候下标要升序排序，样例也是鸡贼，不对下标排序的话能过，然后我就开心的提交了，然后就G了，所以下标也要拍一次序，当然要在选出的那L或者K个大值中排序。

#include<bits/stdc++.h>
using namespace std;
int m,n,k,L,d;
const int M=2e4+5;
struct node{
	int ind,cnt;
	bool operator<(const node &a)const{
		return cnt>a.cnt;
	}
};
bool cmp(node a,node b){
    return a.ind<b.ind;
}
node h[M];
node l[M];
int main(){
	cin>>m>>n>>k>>L>>d;
	for(int i=1;i<=m;i++) h[i].ind=i;
	for(int j=1;j<=n;j++) l[j].ind=j;
	for(int i=1;i<=d;i++){
		int x,y,p,q;
		cin>>x>>y>>p>>q;
		if(y==q) h[((x<p)? x:p)].cnt++;
		if(x==p) l[((y<q)? y:q)].cnt++; 
	}
	sort(h+1,h+1+m);
	sort(l+1,l+1+n);
    sort(l+1,l+1+L,cmp);
    sort(h+1,h+1+k,cmp);
//	for(int i=1;i<=n;i++){
//		cout<<l[i].ind<<" "<<l[i].cnt<<endl;
//	}
	for(int i=1;i<=k;i++){
		cout<<h[i].ind<<" ";
	}
	cout<<'\n';
	for(int i=1;i<=L;i++){
		cout<<l[i].ind<<" ";
	}
	cout<<'\n';
	return 0;
}