A1080 Graduate Admission (30 分)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
struct Stu{
	int no, Ge, Gi, r;
	int choice[7];
}stu[40010];
int N, M, K;
const int maxn = 99999;
struct School{
	int quota, r, flag;
	int adm[40010];
}sch[110];
bool cmp(Stu s1, Stu s2){
	int n1 = s1.Ge + s1.Gi;
	int n2 = s2.Ge + s2.Gi;
	if(n1 != n2) return n1 > n2;
	return s1.Ge > s2.Ge; 
}
void Rank(){
	stu[0].r = 1;
	for(int i = 2; i <= N; i++){
		int n1 = stu[i-1].Ge + stu[i-1].Gi;
		int n2 = stu[i-1-1].Ge + stu[i-1-1].Gi;
	
		if(n1 == n2 && stu[i-1].Ge == stu[i-1-1].Ge){
			stu[i-1].r = stu[i-1-1].r;
		}else stu[i-1].r = i;
	}
}
int main(){	
	scanf("%d %d %d", &N, &M, &K);
	for(int i = 0; i < M; i++){
		scanf("%d", &sch[i].quota);
		sch[i].r = 0; sch[i].flag = maxn;
		memset(sch[i].adm, 0, sizeof(sch[i].adm));
	}	
	for(int i = 0; i < N; i++){
		scanf("%d %d", &stu[i].Ge, &stu[i].Gi);
		stu[i].no = i;
		for(int j = 0; j < K; j++){
			scanf("%d", &stu[i].choice[j]);
		}
	}
	sort(stu, stu+N, cmp);
	Rank();
	for(int i = 0; i < N; i++){
		for(int j = 0; j < K; j++){
			int pos = stu[i].choice[j];
			if(sch[pos].quota > 0 || sch[pos].r == stu[i].r){
				sch[pos].adm[stu[i].no] = 1;
				sch[pos].quota--;
				sch[pos].flag = min(sch[pos].flag, stu[i].no);
				sch[pos].r = max(sch[pos].r, stu[i].r);
				break;
			}
		} 
	}
	for(int i = 0; i < M; i++){
		if(sch[i].flag == maxn){
			putchar('\n'); continue;
		}
		printf("%d", sch[i].flag);
		for(int j = sch[i].flag + 1; j < 40010; j++){
			if(sch[i].adm[j] == 1){
				printf(" %d", j);
			}
		}putchar('\n');
	}
	return 0;
}

 

上一篇:S210 扭矩限幅模式 屏蔽 7900


下一篇:基于单片机的多任务轮询系统