P1056 排座椅

P1056 排座椅 题目描述 解题思路

在排座椅问题里，有一个问题，然而并没有在图中表示出来，在划分通道时要优先划分隔开同学最多的通道。所以在代码里我会用哈希法来存储在划分时隔开的同学对数。

AC代码

#include 
#include 
#include 
using namespace std;
struct _struct1{
	int x1,x2,y1,y2;
}a[2005]; 
struct _struct2{
	int num;
	int i;
}x[2005],y[2005];
bool cmp1(_struct2 x,_struct2 y){
	return x.num > y.num;
}
bool cmp2(_struct2 x,_struct2 y){ 
	return x.i < y.i;
}
int main () {
	int m,n,k,l,d;
	cin >> m >> n >> k >> l >> d;
	for (int i = 1;i <= m;i++){
		x[i].i = i;
	} 
	for (int i = 1;i <= n;i++){
		y[i].i = i;
	}
	for (int i = 1;i <= d;i++){
		cin >> a[i].x1 >> a[i].x2 >> a[i].y1 >> a[i].y2;
		if (a[i].x2 != a[i].y2){
			y[min(a[i].x2,a[i].y2)].num += 1;
		}
		if (a[i].x1 != a[i].y1){
			x[min(a[i].x1,a[i].y1)].num += 1;
		}
	}
	sort(x+1,x+m+1,cmp1);
	sort(y+1,y+n+1,cmp1);
	sort(x+1,x+k+1,cmp2);
	sort(y+1,y+l+1,cmp2);
	for (int i = 1;i < k;i++){
		cout << x[i].i << " ";	}
	cout << x[k].i << endl;
	for (int i = 1;i < l;i++){
		cout << y[i].i << " ";
	}
	cout << y[l].i;
	return 0;
}

（2008年普及组第二题）

拜拜！