UVa 10249 The Grand Dinner

題意：
　　有M個隊伍以及N張桌子，每個隊伍的人數與每張桌子的座位均不一樣，現在要將同個隊伍的隊員分配到不同的桌子(同隊的不能在同張桌子，否則輸出0)
想法：

1. 每個隊伍的隊員排的時候都先挑剩餘位子最多的桌子
2. 如果該隊隊伍人數大於桌子數量或是座位不足則跳出並print 0

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct temp_type{
	int *t;
	int index;
	}temp[51];
	bool cmp(temp_type a,temp_type b){
	return *(a.t)>*(b.t);
	}
	int main()
	{
	int M,N; //M:number of teams, N:number of tables
	int m[71],n[51]; //m:number of members of a team, n:seating capacity of a table
	while (scanf("%d %d",&M,&N)){
	if (!M && !N) break;
	int i,j,ans[71][100];
	for(i=0;i<M;i++) scanf("%d",&m[i]);
	for(i=0;i<N;i++) scanf("%d",&n[i]);
	bool ok=1;
	for(i=0;i<M && ok;i++){
	if(m[i]>N) {ok=0; break;} //隊員數量大於桌子數量
	//將桌子的座位數量與index複製到temp
	//並依照剩餘座位數量排序
	for(j=0;j<N;j++) {
	temp[j].t=&n[j];
	temp[j].index=j;
	}
	sort(temp,temp+N,cmp);
	int n_ans=0;
	//隊員m[i]個，排入剩餘位子前m[i]多的桌子
	for(j=0;j<m[i];j++){
	if(*(temp[j].t)<=0) {ok=0; break;}
	else {
	(*(temp[j].t))--;
	ans[i][n_ans++]=temp[j].index;
	}
	}
	sort(ans[i],ans[i]+n_ans); //將index由小排到大
	}
	if(ok){
	printf("1\n");
	for(i=0;i<M;i++) {
	for(j=0;j<m[i];j++)
	printf("%d ",ans[i][j]+1);
	printf("\n");
	}
	}
	else printf("0\n");
	}
	return 0;
	}

view raw [UVa] 10249 The Grrand Dinner.cpp hosted with ❤ by GitHub