先对学生们进行排序,并且求出对应排名。
对于每一个学生,按照志愿的顺序:
1.如果学校名额没满,那么便被该学校录取,并且另vis[s][app[i].ranks]=1,表示学校s录取了该排名位置的学生。
2.如果该学校名额已满,那么看看vis[s][app[i].ranks]是否为1,若是,则表明学校有录取过和他排名一样的学生,那么该学生也能被录取。
否则,学生未录取。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector> using namespace std;
const int maxn=;
const int maxschool=;
int quota[maxschool];
vector<int> res[maxschool];
int app_school[maxn];
int vis[maxschool][maxn]; //vis[s][i]=1表示学校s有录取rank为i的学生
struct Applicant{
int id;
int ranks;
int GE,GI;
float grades;
int choose[];
bool operator<(const Applicant tmp)const{
if(grades==tmp.grades){
return GE>tmp.GE;
}
else
return grades>tmp.grades;
}
}app[maxn]; int main()
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
for(int i=;i<m;i++){
scanf("%d","a[i]);
}
for(int i=;i<n;i++){
scanf("%d %d",&app[i].GE,&app[i].GI);
for(int j=;j<k;j++){
scanf("%d",&app[i].choose[j]);
}
app[i].id=i;
app[i].grades=(app[i].GE+app[i].GI)/2.0f;
}
sort(app,app+n);
int cnt=;
for(int i=;i<n;i++){
app[i].ranks=++cnt;
for(int j=i+;j<n;j++){
if(app[i].grades==app[j].grades && app[i].GE==app[j].GE){
app[j].ranks=cnt;
i++;
}
}
} //for(int i=0;i<n;i++){
// printf("ranks:%d %d %f %d\n",app[i].GE,app[i].GI,app[i].grades,app[i].ranks);
//}
memset(vis,,sizeof(vis));
int lastSchool=;
int last=;
for(int i=;i<n;i++){
app_school[i]=-;
int j;
for(j=;j<k;j++){
int s=app[i].choose[j];
if(quota[s]>){
quota[s]--;
res[s].push_back(app[i].id);
//lastSchool=s;
//last=i;
app_school[i]=s;
//printf("app:%d school:%d\n",app[i].id,s);
vis[s][app[i].ranks]=;
break;
}
else{
//只要有rank一样的选了这所学校,即使没有名额,那么该生也可以被录取
if(vis[s][app[i].ranks]){
app_school[i]=s;
res[s].push_back(app[i].id);
break;
}
}
}
}
for(int i=;i<m;i++){
int num=res[i].size();
if(num==)
printf("\n");
else{
sort(res[i].begin(),res[i].end());
printf("%d",res[i][]);
for(int j=;j<num;j++){
printf(" %d",res[i][j]);
}
printf("\n");
}
}
return ;
}