排座椅[NOIP2008 年普及组]：贪心

解题思路:贪心策略， 分隔最多同学对数倒序排列， 选取前k（l）个加入vector, 然后以Idx排序输出

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10; 
struct node{
	int cnt, idx;
}x[N], y[N];
int m, n, k, l, d, xx, yy, x2, y2;
bool cmp(node a, node b) {
	if(a.cnt == b.cnt) return a.idx < b.idx;
	return a.cnt > b.cnt;
}
bool cmp1(node a, node b){
	if(a.idx == b.idx) return a.cnt > b.cnt;
	return a.idx < b.idx;
}
vector<node> resx, resy;
int main()
{
	cin >> m >> n >> k >> l >> d;
	for(int i = 0; i < d; ++ i){
		cin >> xx >> yy >> x2 >> y2;
		if(xx == x2 ) {
			y[min(yy, y2)].cnt ++;
			y[min(yy, y2)].idx = min(yy, y2);
		}
		else {
			x[min(xx, x2)].cnt ++;
			x[min(xx, x2)].idx = min(xx, x2);
		}
	}
	sort(x,x + m + 1, cmp);
	sort(y,y + n + 1, cmp);
	for(int i = 0; i < k; ++ i)
		resx.push_back(x[i]);
	for(int i = 0; i < l; ++ i)
		resy.push_back(y[i]);
	sort(resx.begin(),resx.end(), cmp1);
	sort(resy.begin(),resy.end(), cmp1);
	for(auto i:resx)
		cout << i.idx << ' ';
	cout << endl;
	for(auto i:resy)
		cout << i.idx << ' ';	
	return 0;
}