It is said that in 2013, there were about 100 graduate schools ready to proceed over 40,000 applications in Zhejiang Province. It would help a lot if you could write a program to automate the admission procedure.
Each applicant will have to provide two grades: the national entrance exam grade GE, and the interview grade GI. The final grade of an applicant is (GE + GI) / 2. The admission rules are:
Input Specification:
Each input file contains one test case. Each case starts with a line containing three positive integers: N (<=40,000), the total number of applicants; M (<=100), the total number of graduate schools; and K (<=5), the number of choices an applicant may have.
In the next line, separated by a space, there are M positive integers. The i-th integer is the quota of the i-th graduate school respectively.
Then N lines follow, each contains 2+K integers separated by a space. The first 2 integers are the applicant‘s GE and GI, respectively. The next K integers represent the preferred schools. For the sake of simplicity, we assume that the schools are numbered from 0 to M-1, and the applicants are numbered from 0 to N-1.
Output Specification:
For each test case you should output the admission results for all the graduate schools. The results of each school must occupy a line, which contains the applicants‘ numbers that school admits. The numbers must be in increasing order and be separated by a space. There must be no extra space at the end of each line. If no applicant is admitted by a school, you must output an empty line correspondingly.
Sample Input:11 6 3 2 1 2 2 2 3 100 100 0 1 2 60 60 2 3 5 100 90 0 3 4 90 100 1 2 0 90 90 5 1 3 80 90 1 0 2 80 80 0 1 2 80 80 0 1 2 80 70 1 3 2 70 80 1 2 3 100 100 0 2 4Sample Output:
0 10 3 5 6 7 2 8 1 4
#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX 105
using namespace std;
typedef struct Stu
{
int num;
int Ge;
int Gi;
int choice[5];
int rank;
}Stu;
int cmp(const Stu &l,const Stu &r)
{
if(l.Ge+l.Gi==r.Ge+r.Gi)
return l.Ge>r.Ge;
else
return l.Ge+l.Gi>r.Ge+r.Gi;
}
int main(int argc,char *argv[])
{
int n,m,k;
int Quota[MAX];
int Rankmark[MAX];
vector<int> Admit[MAX];
int i,j;
vector<Stu> v;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<m;i++)
scanf("%d",&Quota[i]);
for(i=0;i<n;i++)
{
Stu temp;
temp.num=i;
scanf("%d%d",&temp.Ge,&temp.Gi);
for(j=0;j<k;j++)
scanf("%d",&temp.choice[j]);
v.push_back(temp);
}
sort(v.begin(),v.end(),cmp);
int sum1,sum2;
v[0].rank=1;
sum1=v[0].Ge+v[0].Gi;
for(i=1;i<n;i++)
{
sum2=v[i].Ge+v[i].Gi;
if(sum2<sum1)
v[i].rank=v[i-1].rank+1;
else if(sum2==sum1&&v[i].Ge<v[i-1].Ge)
v[i].rank=v[i-1].rank+1;
else if(sum2==sum1&&v[i].Ge==v[i-1].Ge)
v[i].rank=v[i-1].rank;
sum1=sum2;
}
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
{
int index=v[i].choice[j];
if(Admit[index].size()<Quota[index])
{
Admit[index].push_back(v[i].num);
Rankmark[index]=v[i].rank;
break;
}
else if(v[i].rank==Rankmark[index])
{
Admit[index].push_back(v[i].num);
break;
}
}
}
for(i=0;i<m;i++)
{
sort(Admit[i].begin(),Admit[i].end());
if(Admit[i].size()==0)
printf("\n");
else
{
for(j=0;j<Admit[i].size();j++)
{
if(j==0)
printf("%d",Admit[i][j]);
else
printf(" %d",Admit[i][j]);
}
printf("\n");
}
}
return 0;
}
AC代码：（二）不用计算出排名#include<cstdio>
#include<vector>
#include<algorithm>
#define MAX 105
using namespace std;
typedef struct Stu
{
int num;
int Ge;
int Gi;
int choice[5];
}Stu;
int cmp(const Stu &l,const Stu &r)
{
if(l.Ge+l.Gi==r.Ge+r.Gi)
return l.Ge>r.Ge;
else
return l.Ge+l.Gi>r.Ge+r.Gi;
}
int main(int argc,char *argv[])
{
int n,m,k;
int Quota[MAX];
int Vacancy[MAX];
vector<int> Admit[MAX];
Stu s[40005];
int i,j;
vector<Stu> v;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<m;i++)
{
scanf("%d",&Quota[i]);
Vacancy[i]=Quota[i];
}
for(i=0;i<n;i++)
{
Stu temp;
temp.num=i;
scanf("%d%d",&temp.Ge,&temp.Gi);
for(j=0;j<k;j++)
scanf("%d",&temp.choice[j]);
v.push_back(temp);
s[i]=temp;
}
sort(v.begin(),v.end(),cmp);
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
{
int index=v[i].choice[j];
if(Vacancy[index]>=1)
{
Admit[index].push_back(v[i].num);
Vacancy[index]--;
break;
}
else if(Vacancy[index]==0)
{
int t=Admit[index].back();
if(s[t].Ge+s[t].Gi==v[i].Ge+v[i].Gi&&v[i].Ge==s[t].Ge)
{
Admit[index].push_back(v[i].num);
break;
}
}
}
}
for(i=0;i<m;i++)
{
sort(Admit[i].begin(),Admit[i].end());
if(Admit[i].size()==0)
printf("\n");
else
{
for(j=0;j<Admit[i].size();j++)
{
if(j==0)
printf("%d",Admit[i][j]);
else
printf(" %d",Admit[i][j]);
}
printf("\n");
}
}
return 0;
}
Pat(Advanced Level)Practice--1080(Graduate Admission),布布扣,bubuko.com
Pat(Advanced Level)Practice--1080(Graduate Admission)
原文：http://blog.csdn.net/cstopcoder/article/details/22432099