P1056 排座椅 （贪心&排序)

P1056 排座椅 （贪心&排序)

题目传送门

思路：分别求出分割每行每列的同学对数，然后排序，分别取k和l个即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5; 
struct p{
	int id,v;
}a[N],b[N];
bool cmp(p a,p b){
	return a.v>b.v;
}
int vis[N][2];
int main(){
	int n,m,k,l,d;
	cin>>n>>m>>k>>l>>d;
	for(int i=1,x1,y1,x2,y2;i<=d;i++){
		 cin>>x1>>y1>>x2>>y2;
		 if(y1==y2) a[min(x1,x2)].v++,a[min(x1,x2)].id=min(x1,x2);//printf("a[%d]",min(x1,x2));
		 else b[min(y1,y2)].v++,b[min(y1,y2)].id=min(y1,y2);//printf("b[%d]",min(y1,y2));
	}
	sort(a+1,a+N,cmp);
	sort(b+1,b+N,cmp);
	for(int i=1;i<=l;i++)
		vis[b[i].id][1]=1;
		for(int i=1;i<=k;i++)
		vis[a[i].id][0]=1;
	for(int i=1,j=1;i<n;i++)
			if(vis[i][0])
			printf(j++==k?"%d\n":"%d ",i);
	for(int i=1,j=1;i<m;i++)
			if(vis[i][1])
			printf(j++==l?"%d\n":"%d ",i);		
	return 0;	
}