首页 > 试题广场 >

Graduate Admission

[编程题]Graduate Admission
  • 热度指数：2014 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
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:

  • The applicants are ranked according to their final grades, and will be admitted one by one from the top of the rank list.
  • If there is a tied final grade, the applicants will be ranked according to their national entrance exam grade GE. If still tied, their ranks must be the same.
  • Each applicant may have K choices and the admission will be done according to his/her choices: if according to the rank list, it is one's turn to be admitted; and if the quota of one's most preferred shcool is not exceeded, then one will be admitted to this school, or one's other choices will be considered one by one in order. If one gets rejected by all of preferred schools, then this unfortunate applicant will be rejected.
  • If there is a tied rank, and if the corresponding applicants are applying to the same school, then that school must admit all the applicants with the same rank, even if its quota will be exceeded.

    • 输入描述:
    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.


    输出描述:
    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.
    示例1

    输入

    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 4

    输出

    0 10
3
5 6 7
2 8

1 4
    算法知识视频讲解
    添加回答
    C/C++
    纠结offer的菜狗头像 纠结offer的菜狗 
    #include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

typedef struct Info
{
    int num,ge,gi,rank;
    int choice[5];
    bool operator <(const Info &t) const
    {
        if(ge + gi != t.ge + t.gi) return ge + gi > t.ge + t.gi;
        return ge > t.ge;
    }
}Info;

Info info[40001];
int quota[101];

int main()
{
    int N,M,K;
    cin >> N >> M >> K;
    for(int i = 0;i < M;i++)
    {
        cin >> quota[i];
    }
    for(int i = 0;i < N;i++)
    {
        info[i].num = i;
        cin >> info[i].ge >> info[i].gi;
        for(int j = 0;j < K;j++)
        {
            cin >> info[i].choice[j];
        }
    }
    sort(info,info + N);
    info[0].rank = 0;
    for(int i = 1;i < N;i++)
    {
        if(info[i].ge + info[i].gi == info[i - 1].ge + info[i - 1].gi && info[i].ge == info[i - 1].ge)
        {
            info[i].rank = info[i - 1].rank;
        }
        else
        {
            info[i].rank = info[i - 1].rank + 1;
        }
    }
    vector<int> admit[M];
    int last_rank[M];
    fill(last_rank,last_rank + M,-1);
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < K;j++)
        {
            if(quota[info[i].choice[j]])
            {
                admit[info[i].choice[j]].push_back(info[i].num);
                quota[info[i].choice[j]]--;
                last_rank[info[i].choice[j]] = info[i].rank;
                break;
            }
            else if(last_rank[info[i].choice[j]] == info[i].rank)
            {
                admit[info[i].choice[j]].push_back(info[i].num);
                break;
            }
        }
    }
    for(int i = 0;i < M;i++)
    {
        sort(admit[i].begin(),admit[i].end());
        for(auto ad : admit[i])
        {
            cout << ad << " ";
        }
        cout << endl;
    }
    return 0;
}

    发表于 2021-02-21 13:20:47 回复(0)
    星星mage头像 星星mage
    注意：
    1.按照排名从上到下，每个考生尝试从前到后选择自己的各个志愿直到录取
    2.不是保护第一志愿
    录取的条件：目标院校有名额或者考生的成绩不小于已经录取的最后一名

    用C++写的还算比较简洁易懂的代码： 
    #include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;
struct Applicant {
    int id;
    int Ge, Gi;
    double Gf;
    vector<int> Choices;
    bool operator<(const Applicant& a) const {
        return Gf > a.Gf || (Gf == a.Gf && Ge > a.Ge);
    };
};
struct EnrollInfo {
    vector<int> StList;
    int bottom;  //录取的成绩最低的学生
    EnrollInfo() : bottom(-1) {}
};

int main() {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vector<int> Quotas(M);
    for (auto& q : Quotas) scanf("%d", &q);
    vector<Applicant> Apps(N);
    for (int i = 0; i < N; ++i) {
        scanf("%d %d", &Apps[i].Ge, &Apps[i].Gi);
        Apps[i].Gf = (Apps[i].Ge + Apps[i].Gi) / (double)2;
        Apps[i].id = i;
        Apps[i].Choices.resize(K);
        for (auto& c : Apps[i].Choices) scanf("%d", &c);
    }
    sort(Apps.begin(), Apps.end());
    //按照排名从上往下进行学校选择,目标院校有名额的或者该生的排名不低于目标院校的最低成绩，则录取
    vector<EnrollInfo> Res(M);
    for (int st = 0; st < N; ++st) {
        for (auto& sc : Apps[st].Choices) {
            if (Quotas[sc] > 0 || !(Apps[Res[sc].bottom] < Apps[st])) {
                Res[sc].bottom = st;
                Res[sc].StList.push_back(Apps[st].id);
                --Quotas[sc];
                break;
            }
        }
    }
    for (auto& r : Res) {
        if (!r.StList.empty()) {
            sort(r.StList.begin(), r.StList.end());
            printf("%d", r.StList.front());
        }
        for (size_t i = 1; i < r.StList.size(); ++i) {
            printf(" %d", r.StList[i]);
        }
        printf("\n");
    }
    return 0;
}


    编辑于 2020-06-29 23:34:16 回复(0)
    捞捞我，球球了头像 捞捞我，球球了
    利用好结构体 进行储存，再利用sort快速排序，成功AC.
    #include<iostream>
#include<algorithm>
using namespace std;
struct student {
    int id;
    float ge;
    float g1;
    float grade;
    int wish[5];
};
struct school{
    int per;
    int temp;
    student people[500];
};
bool cmp1(student a,student b){
    return a.id<b.id;
}
bool cmp(student a,student b){
    if(a.grade==b.grade){
        return a.ge>b.ge;
    };
    return a.grade>b.grade;
}
int main(){
    int n;
    while(cin>>n){//信息存储
        student *stu=new student[n];
        int m,k;
        cin>>m>>k;
        school *sch=new school[m];
       for(int i=0;i<m;i++){
           cin>>sch[i].per;
           sch[i].temp=0;
       } 
        for(int i=0;i<n;i++){
            stu[i].id=i;
            cin>>stu[i].ge>>stu[i].g1;
            stu[i].grade=(stu[i].ge+stu[i].g1)/2;
            for(int j=0;j<k;j++){
            cin>>stu[i].wish[j];
        }
    }
        //信息处理
        sort(stu,stu+n,cmp);//对学生进行排序
        for(int i=0;i<n;i++){
            for(int j=0;j<k;j++){
                if(sch[stu[i].wish[j]].temp>0)
                if(sch[stu[i].wish[j]].people[sch[stu[i].wish[j]].temp-1].ge==stu[i].ge&&sch[stu[i].wish[j]].people[sch[stu[i].wish[j]].temp-1].g1==stu[i].g1){
                    sch[stu[i].wish[j]].people[sch[stu[i].wish[j]].temp++]=stu[i];
                    break;
                }
                if(sch[stu[i].wish[j]].temp<sch[stu[i].wish[j]].per){
                    sch[stu[i].wish[j]].people[sch[stu[i].wish[j]].temp++]=stu[i];
                    break;
                }
                
            }
        }
        for(int i=0;i<m;i++){
            sort(sch[i].people,sch[i].people+sch[i].temp,cmp1);
            for(int j=0;j<sch[i].temp;j++){
                cout<<sch[i].people[j].id<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}

    发表于 2019-11-27 19:54:30 回复(0)
    沉默の鱼头像 沉默の鱼 
    #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
    
struct StuInfo {
    int number, Ge, sumGrade, rank;
    bool operator < (const StuInfo a) const {
        return (sumGrade > a.sumGrade) || (sumGrade == a.sumGrade && Ge > a.Ge);
    }
};
    
int N, M, K;
vector<vector<int> > preList, result;
vector<StuInfo> student;
vector<int> quota, lastAdmitRank;
int main(void) {
    ios::sync_with_stdio(false);
    cin >> N >> M >> K;
    preList.resize(N);
    student.resize(N);
    quota.resize(M);
    lastAdmitRank.resize(M);
    result.resize(M);
    for (int i = 0; i < M; i++){
        cin >> quota[i];
        lastAdmitRank[i] = -1;
    }
    for (int i = 0; i < N; i++) {
        int Gi;
        cin >> student[i].Ge >> Gi;
        student[i].sumGrade = student[i].Ge + Gi;
        student[i].number = i;
        preList[i].resize(K);
        for (int j = 0; j < K; j++)
            cin >> preList[i][j];
    }
    sort(student.begin(), student.end());
    int lastSumGrade = -1, lastGe = -1, rank = 0;
    for(int i = 0; i < N; i++){
        if(lastSumGrade == student[i].sumGrade && lastGe == student[i].Ge)
            student[i].rank = rank;
        else
            student[i].rank = ++rank;
        lastSumGrade = student[i].sumGrade;
        lastGe = student[i].Ge;
    }
    for(int i = 0; i < N; i++){
        for(int j = 0; j < K; j++){
            int prefer = preList[student[i].number][j];
            if(quota[prefer] > 0 || lastAdmitRank[prefer] == student[i].rank){
                result[prefer].push_back(student[i].number);
                quota[prefer]--;
                lastAdmitRank[prefer] = student[i].rank;
                break;
            }
        }
    }
    for(int i = 0; i < M; i++){
        bool first = true;
        sort(result[i].begin(), result[i].end());
        for(int j = 0; j < result[i].size(); j++){
            if(first){
                first = false;
                cout << result[i][j];
            }
            else
                cout << " " << result[i][j];
        }
        cout << endl;
    }
    return 0;
}
    基本思路：12ms...很平常的思路，依据成绩排序后再为每个学生设定rank，并且为每个学校设置了一个lastAdmitRank的数组，用来避免等级1，1，1排序的学生出现1，2，1选择学校出错的情况，结果存于result数组中输出
    编辑于 2019-03-06 12:46:02 回复(0)
    C/C++
    jackma23333头像 jackma23333 
    #include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define maxn 40010
#define maxm 110
int n,m,k;
struct student{
	int idx,ge,gi,ga,rank,app[5];
}stu[maxn];
int school[maxm];
queue<int> q,qt;
int result[maxm][maxn];
int Count[maxm]={0};
bool Hashtable[maxm]={false};
bool cmp(student a,student b){
	if(a.ga!=b.ga)return a.ga>b.ga;
	else return a.ge>b.ge;
}
void admit(int x){
	for(int i=0;i<k;i++){
		int temp=stu[x].app[i];
		if(school[temp]>0||Hashtable[temp]){
			result[temp][Count[temp]++]=(stu[x].idx);
			Hashtable[temp]=true;
			qt.push(temp);
			school[temp]--;
			break;
		}
	}
}
int main(){
	//freopen("A1080.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++)scanf("%d",&school[i]);
	for(int i=0;i<n;i++){
		stu[i].idx=i;
		scanf("%d%d",&stu[i].ge,&stu[i].gi);
		stu[i].ga=stu[i].ge+stu[i].gi;
		for(int j=0;j<k;j++)scanf("%d",&stu[i].app[j]);
	}
	sort(stu,stu+n,cmp);
	stu[0].rank=0;
	q.push(0);
	for(int i=1;i<=n;i++){
		if(stu[i].ga==stu[i-1].ga&&stu[i].ge==stu[i-1].ge&&i<n){
			stu[i].rank=stu[i-1].rank;
			q.push(i);
		}
		else{
			while(!q.empty()){
				int temp=q.front();
				admit(temp);
				q.pop();
			}
			while(!qt.empty()){
				int temp=qt.front();
				Hashtable[temp]=false;
				qt.pop();
			}
			stu[i].rank=i;
			q.push(i);
		}
	}
	for(int i=0;i<m;i++){
		int temp=Count[i];
		if(temp>0)sort(result[i],result[i]+temp);
		for(int j=0;j<temp;j++){
			printf("%d",result[i][j]);
			if(j<temp-1)printf(" ");
		}
		printf("\n");
	}
}
    注意在测试点4的数据可能超时，尽量不要用容器来存储学校的录取名单
    还可以参考解题思路
    https://www.sigmainfy.com/blog/pat-1080-graduate-admission.html
    发表于 2017-08-20 21:56:40 回复(0)
    C++
    想去大厂干开发头像 想去大厂干开发 
    #include <iostream>
#include "algorithm"
#include <vector>
using namespace std;

struct Applicant{
    int num, rank;  //记录初始编号和排名
    float GE, GI ,final;    //记录成绩
    vector<int> target;     //目标院校
};

struct School{
    int quato;  //配额
    vector<Applicant> ac;   //记录已录取的学生
};

bool cmp(Applicant lhs, Applicant rhs){     //按成绩排序
    return lhs.final > rhs.final || lhs.final == rhs.final && lhs.GE > rhs.GE;
}

bool cmp2(Applicant lhs, Applicant rhs){    //升序输出编号
    return lhs.num < rhs.num;
}

int main(){
    int n, m, k;
    while(cin >> n >> m >> k){
        //输入数据
        School sc[m];
        for(int i=0; i<m; ++i){
            cin >> sc[i].quato;
        }
        Applicant appl[n];
        int temp;
        for(int i=0; i<n; ++i){
            cin >> appl[i].GE >> appl[i].GI;
            appl[i].final = (appl[i].GI + appl[i].GE)/2;
            appl[i].num = i;
            for(int j=0; j<k; ++j){
                cin >> temp;
                appl[i].target.push_back(temp);
            }
        }
        //按成绩排序并给出相应排名，总分及初试同分则同排名
        sort(appl, appl+n, cmp);
        appl[0].rank = 0;
        for(int i=1; i<n; ++i){
            if(appl[i-1].final == appl[i].final && appl[i-1].GE == appl[i].GE){
                appl[i].rank = appl[i-1].rank;
            }else{
                appl[i].rank = i;
            }
        }
        //按排名录取，顺着志愿表依次判断目标院校是否有名额或者最后一位录取者是否与自己同排名
        for(int i=0; i<n; ++i){
            for(int j=0; j<k; ++j){
                if(sc[appl[i].target[j]].quato>0 || sc[appl[i].target[j]].ac.back().rank == appl[i].rank){
                    sc[appl[i].target[j]].ac.push_back(appl[i]);
                    sc[appl[i].target[j]].quato--;
                    break;
                }
            }
        }
        //按院校编号输出各院校录取名单
        for(int i=0; i<m; ++i){
            if(sc[i].ac.empty()){
                cout << endl;
            }else{
                sort(sc[i].ac.begin(), sc[i].ac.end(), cmp2);
                for(int j=0; j<sc[i].ac.size()-1; ++j){
                    cout << sc[i].ac[j].num << ' ';
                }
                //题目要求每行最后不能有多余的空格
                cout << sc[i].ac[sc[i].ac.size()-1].num << endl;
            }
        }
    }
}

    编辑于 2024-03-13 21:20:35 回复(0)
    写bug的大师头像 写bug的大师
    10 / 11代码 
    #include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
using namespace std;
const int MAXN = 110;

typedef struct Student {
	double g1;
	double g2;
	double g3;
	int sno;
	vector<int> zy;
} Student;
vector<Student> ss;
int arr[MAXN];
vector<vector<int>> b;

bool cmp(Student a, Student b) {
	if (abs(a.g3 - b.g3) >= 1e-5) { // double 比较等号
		return a.g3 > b.g3;
	}
	if (abs(a.g1 - b.g1) >= 1e-5) {
		return a.g1 > b.g1;
	}
	return a.sno < b.sno;
}

int main() {
	int n, m, k;
	while (cin >> n >> m >> k) { // n为申请人数 m为学校数 k为自愿数
		ss.clear();
		b.clear();
		for (int i = 0; i < m; i++) {
			cin >> arr[i];
			vector<int> o;
			b.push_back(o); //新建
		}
		for (int i = 0; i < n; i++) {
			Student s;
			cin >> s.g1 >> s.g2;
			s.g3 = (s.g1 + s.g2) / 2;
			vector<int> zy;
			for (int j = 0; j < k; j++) {
				int a;
				cin >> a;
				zy.push_back(a);
			}
			s.zy = zy;
			s.sno = i;
			ss.push_back(s);
		}
		sort(ss.begin(), ss.end(), cmp);
		int pre = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < k; j++) {
				if (arr[ss[i].zy[j]] > 0) {
					b[ss[i].zy[j]].push_back(ss[i].sno);
					arr[ss[i].zy[j]] -= 1;
					break;
                }
				// } else {
				// 	int num = b[ss[i].zy[j]][b[ss[i].zy[j]].size() - 1];
				// 	if (abs(ss[num].g3 - ss[i].g3) <= 1e-4 && abs(ss[num].g1 - ss[i].g1) <= 1e-4) { // 破格录取
				// 		b[ss[i].zy[j]].push_back(ss[i].sno);
				// 	}
				// }
			}
		}
		for (int i = 0; i < m; i++) {
			if (b[i].size() == 0) {
				cout << endl;
			} else {
				sort(b[i].begin(), b[i].end());
				for (int j = 0; j < b[i].size() - 1; j++) {
					cout << b[i][j] << " ";
				}
				cout << b[i][b[i].size() - 1] << endl;
			}
		}
	}
	return 0;
}


    编辑于 2024-03-04 15:28:04 回复(0)
    C/C++
    None_to_None头像 None_to_None 
    #include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct stu{
    int num;
    double ge, grade;
    int rank;
    vector<int> ch;
};

bool cmp(stu a, stu b){
    if(a.grade!= b.grade) return a.grade>b.grade;
    else return a.ge>b.ge;
}

int main(){
    int stun, unin, k;
    double gt;
    cin>>stun>>unin>>k;
    vector<int> quota(unin);
    vector<int> ranks(unin);
    vector<stu> s(stun);
    vector<int> res[unin];
    
    //学校招生人数
    for(int i=0; i<unin; i++)
        cin>>quota[i];
    
    //输入学生信息
    for(int i=0; i<stun; i++){
        cin>>s[i].ge>>gt;
        s[i].num=i;
        s[i].grade=(s[i].ge+gt)/2;
        
        int tmp;
        for(int j=0; j<k; j++){
            cin>>tmp;
            s[i].ch.push_back(tmp);
        }
    }
    
    //根据成绩对学生进行排序
    sort(s.begin(), s.end(), cmp);
    
    //给学生排名；如果和上一名学生成绩相同，则排名相同
    s[0].rank=0;
    for(int i=1; i<s.size(); i++){
        if(s[i].grade==s[i-1].grade && s[i].ge==s[i-1].ge)
            s[i].rank=s[i-1].rank;
        else s[i].rank=i;
    }
    
    //录取学生；
    //按照排名从高到低，对每个学生的志愿进行判断
    //若志愿学校招生未满，或者排名与该学校录取学生最低排名相同，则录取
    for(int i=0; i<s.size(); i++){
        for(int j=0; j<k; j++){
            int chnum=s[i].ch[j];
            if(quota[chnum]>0 || ranks[chnum]==s[i].rank){
                quota[chnum]--;
                ranks[chnum]=s[i].rank;
                res[chnum].push_back(s[i].num);
                break;
            }
        }
    }
    
    
    for(int i=0; i<unin; i++){
        sort(res[i].begin(), res[i].end());
        
        if(res[i].size()>0){
            cout<<res[i][0];
            for(int j=1; j<res[i].size(); j++)
                cout<<' '<<res[i][j];
        }
        cout<<endl;
    }
    
    return 0;
}

    发表于 2021-03-13 14:42:02 回复(0)
    薛定谔的猫e头像 薛定谔的猫e 
    #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct yuan{
    int num;
    int lastadmit;
    vector<int> admit;
};

struct stu{
    int index;
    int ge,gi;
    vector<int> csf;
};

bool cmp(stu a,stu b){
    if(a.ge+a.gi != b.ge+b.gi){
        return a.ge + a.gi > b.ge + b.gi;
    }
    return a.ge > b.ge;
}
int main(){
    int n,m,k;
    while(cin >> n >> m >> k){
        if(n == 0) break;
        yuan *arr1 = new yuan[m];
        for(int i = 0;i < m;i++){
            cin >> arr1[i].num;
            arr1[i].lastadmit = -1;
        }
        stu *arr2 = new stu[n];
        int temp;
        for(int i = 0;i < n;i++){
            cin >> arr2[i].ge >> arr2[i].gi;
            arr2[i].index = i;
            for(int j = 0;j < k;j++){
                cin >> temp;
                arr2[i].csf.push_back(temp);
            }
        }
        sort(arr2,arr2+n,cmp);
        for(int i = 0;i < n;i++){
            for(int j = 0;j < k;j++){
                int choose = arr2[i].csf[j];
                if(arr1[choose].num > 0){
                    arr1[choose].num--;
                    arr1[choose].admit.push_back(arr2[i].index);
                    arr1[choose].lastadmit = i;
                    break;
                }else if(arr1[choose].num == 0){
                    if(arr2[i].ge+arr2[i].gi == arr2[arr1[choose].lastadmit].ge+arr2[arr1[choose].lastadmit].gi){
                        if(arr2[i].ge == arr2[arr1[choose].lastadmit].ge){
                            arr1[choose].admit.push_back(arr2[i].index);
                            break;
                        }
                    }
                }
            }
        }
        for(int i = 0;i < m;i++){
            if(arr1[i].admit.size() == 0){
                cout << endl;
            }else{
                sort(arr1[i].admit.begin(),arr1[i].admit.end());
                for(int j = 0;j < arr1[i].admit.size();j++){
                    cout << arr1[i].admit[j];
                    if(j != arr1[i].admit.size() - 1)
                        cout << " ";
                }
                cout << endl;
            }
        }
    }
}

    发表于 2021-03-10 19:34:55 回复(0)
    zbkhzd头像 zbkhzd
    这个超额录取太秀了 
    #include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,k;
    auto cmp=[](vector<int> v1,vector<int> v2){return v1[1]+v1[2]==v2[1]+v2[2]?v1[1]>v2[1]:v1[1]+v1[2]>v2[1]+v2[2];};
    auto cmp1=[](vector<int> v1,vector<int> v2){return v1[0]<v2[0];};
    auto gradeequal=[](vector<int> v1,vector<int> v2){return v1[2]==v2[2]&&v1[1]==v2[1];};
    while(cin>>n>>m>>k)
    {
        vector<vector<int> > student(n,vector<int>(k+3));
        vector<int> quotas(m);
        for(auto &q:quotas)cin>>q;
        for(int i=0;i<n;++i)
        {
            student[i][0]=i;
            cin>>student[i][1]>>student[i][2];
            for(int j=3;j<=k+2;++j)cin>>student[i][j];
        }
        sort(student.begin(),student.end(),cmp);
        vector<vector< vector<int> > > res(m);
        for(int l=0;l<n;++l)
        {
            for(int i=3;i<=k+2;++i)
            {
                if(res[student[l][i]].size()>=quotas[student[l][i]]&&!gradeequal(res[student[l][i]].back(),student[l]))continue;
                res[student[l][i]].push_back(vector<int>(3)={student[l][0],student[l][1],student[l][2]});
                break;
            }
        }
        for(auto &r:res)
        {
            if(!r.empty())
            {
                sort(r.begin(),r.end(),cmp1);
                for(int i=0;i<r.size()-1;++i)cout<<r[i][0]<<" ";
                cout<<r[r.size()-1][0];
            }
            cout<<endl;
        }
    }
    return 0;
}


    发表于 2020-04-17 00:31:16 回复(0)
    C/C++
    Slashyouth头像 Slashyouth 
    #include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    double Ge, Gi, total;
    int id;
    int pick[6];
} student;

typedef struct scholol
{
    int num, des;//录取人数 、招生人数
    int admin[100*2]; // 录取人员名单
} school;

int cmp(const void* a, const void* b)
{
    student *p1=(student*)a, *p2=(student*)b;
    if(p1->total > p2->total)
        return -1;
    else if(p1->total < p2->total)
        return 1;
    if(p1->Ge > p2->Ge)
        return -1;
    else if(p1->Ge < p2->Ge)
        return 1;
    return 0;
}
int cmp2(const void* a, const void* b)
{
    int *p1=(int*)a, *p2=(int*)b;
    return *p1-*p2;
}
int main()
{
    int n, m, k;
    while(scanf("%d %d %d", &n, &m, &k) != EOF)
    {
        student *stu = malloc(sizeof(student)*n);
        school *sch = malloc(sizeof(school)*m);
        for(int i = 0; i < m; i++)
        {
            scanf("%d", &sch[i].des);
            sch[i].num = 0;
        }
        for(int i = 0; i < n; i++)
        {
            scanf("%lf %lf",&stu[i].Ge, &stu[i].Gi);
            stu[i].id=i;
            stu[i].total=(stu[i].Ge+stu[i].Gi)*0.5;
            for(int j = 0; j < k; j++)
                scanf("%d", &stu[i].pick[j]);
        }
        qsort(stu, n, sizeof(student), cmp);
        int t;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < k; j++)
            {
                t=stu[i].pick[j];
                if(sch[t].num < sch[t].des)  //已招生小于指标
                {
                    sch[t].admin[sch[t].num] = i; //排序后的排名，不是该学生的id
                    sch[t].num += 1;
                    break;
                }
                else     //特殊情况同等情况下进行扩招
                {
                    int x = sch[t].admin[sch[t].num - 1]; //目前该学校招生名额的最后一位学生
                    if(cmp(&stu[x], &stu[i]) == 0)
                    {
                        sch[t].admin[sch[t].num]=i;
                        sch[t].num += 1;
                        break;
                    }
                }
            }
        }
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < sch[i].num; j++)
            {
                t = sch[i].admin[j];
                sch[i].admin[j] = stu[t].id;//恢复录取的人对应原先的序号
            }
            qsort(sch[i].admin,sch[i].num,sizeof(int),cmp2);
            for(int j = 0; j < sch[i].num; j++)
            {
                if(j == 0)
                    printf("%d", sch[i].admin[j]);
                else
                    printf(" %d", sch[i].admin[j]);
            }
            printf("\n");
        }
            free(stu);
            free(sch);
    }
    return 0;
}

    编辑于 2020-04-09 15:19:18 回复(0)
    ヾ安然无恙。头像 ヾ安然无恙。 
    import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static class Stu implements Comparable<Stu>{
		int id;
		int ge,gi;
		int[] sch = new int[10];
		public Stu(int a,int b,int c,int[] d) {
			id =a;
			ge = b;
			gi = c;
			sch = d.clone();
		}
		
		@Override
		public int compareTo(Stu o) {
			if((ge+gi) != (o.ge+o.gi)) {
				if((o.ge+o.gi)>(ge+gi))
					return 1;
				else return -1;
			}
			else if(ge != o.ge) {
				if(o.ge>ge)
					return 1;
				else return -1;
			}
			else {
				if(o.gi>gi) return 1;
				return -1;
			}
			
		}
		
	}
	
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n,m,k;
		n = in.nextInt();
		m = in.nextInt();
		k = in.nextInt();
		int[] qouta = new int[105];
		List<Stu> list = new ArrayList<>(); 
		
		for(int i = 0 ; i < m ; i++) qouta[i] = in.nextInt();
		for(int i = 0 ; i < n ; i++) {
			int[] sch = new int[10];
			int a = in.nextInt();
			int b = in.nextInt();
			for(int j = 0 ; j < k ; j++) {
				sch[j]= in.nextInt();
			}
			Stu stu = new Stu(i,a,b,sch);
			list.add(stu);
		}
		Collections.sort(list);
		
		//存放每个学校录取结果
		List<Integer> res[] = new ArrayList[105];
		for(int i = 0 ; i < m ; i++)
			res[i] =new ArrayList<Integer>();
		
		//二维数组，存放上一个录取学生信息；
		double[][] ifo = new double[105][2];
	                
		for(int i = 0 ; i< n ; i++) {
			Stu stu = list.get(i);
			double ge = stu.ge;double gi = stu.gi;
			for(int j = 0 ; j < k ;j++) {
				int a = stu.sch[j];
				if(qouta[a]>0) {
					qouta[a]--;
					res[a].add(stu.id);
					ifo[a][0] = stu.ge;
					ifo[a][1] = stu.gi;
					break;
				}
				else {
					if((ifo[a][0] == stu.ge)&&(ifo[a][1] == stu.gi)) {
						res[a].add(stu.id);
						break;
					}
				}
			}
		}
		for(int i = 0 ; i < m ; i++) {
			Collections.sort(res[i]);
			if(res[i].size() >0) {
				for(int e:res[i]) {
					System.out.printf("%d ",e);
				}
			}
			System.out.println();
		}
		
		
	}

}



停到90.9   说是数组越界等非法情况，有老大能看出哪有问题么，谢谢

    发表于 2020-04-08 08:55:32 回复(0)
    房间头像 房间 
    #include<iostream>
(720)#include<map>
#include<algorithm>
(831)#include<vector>
using namespace std;
struct Student {
	int Ge, Gi, orSe, Se; vector<int> pri; double  fin;
	Student(int _ge, int _gi, double _fin, int _orse, vector<int> _pri) :Ge(_ge),
		Gi(_gi), fin(_fin), orSe(_orse), pri(_pri) {}
	bool operator < (const Student &a) {
		if (this->fin != a.fin)return this->fin > a.fin;
		else return this->Ge > a.Ge;
	}
};
void setSe(vector<Student> &stu) {
	stu[0].Se = 1;
	if (stu.size() > 1) {
		for (int i = 1; i < stu.size(); i++) {
			if (stu[i - 1].fin != stu[i].fin) {
				stu[i].Se = stu[i - 1].Se + 1;
			}
			else {
				if (stu[i - 1].Ge != stu[i].Ge)
					stu[i].Se = stu[i - 1].Se + 1;
				else stu[i].Se = stu[i - 1].Se;
			}
		}
	}
}
bool cmp(Student &a, Student &b) {
	return a.orSe < b.orSe;
}
int main() {
	int N, M, K;
	while (cin >> N >> M >> K) {
		vector<int> quota;
		for (int i = 0; i < M; i++) {
			int tmp; cin >> tmp;
			quota.push_back(tmp);
		}
		vector<Student> stus;
		for (int i = 0; i < N; i++) {
			int ge, gt; vector<int>pri;
			cin >> ge >> gt;
			for (int j = 0; j < K; j++) {
				int tmp; cin >> tmp;
				pri.push_back(tmp);
			}
			Student stu (ge, gt, static_cast<double>( (ge + gt)) / 2.0f, i, pri);
			stus.push_back(stu);
		}
		sort(stus.begin(), stus.end());
		setSe(stus);
		//according to se to enroll student
		//if the tied rank and same school both enroll
		//no matter insufficient quota
		map<int, vector<Student> > res;
		//inital res
		for (int i = 0; i < M; i++) {
			vector<Student> su;
			res[i] = su;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < K; j++) {
				int snum = stus[i].pri[j];
				if (quota[snum] > 0) {
					res[snum].push_back(stus[i]);
					--quota[snum];
					break;
				}
				//excute tied rank 
				else if (res[snum][res[snum].size() - 1].Se == stus[i].Se)
				{
						res[snum].push_back(stus[i]); break;
				}
			}
		}
		
		for (int i = 0; i < M; i++) {
			if (res[i].size() != 0) {
				sort(res[i].begin(), res[i].end(), cmp);
				for (int j = 0; j < res[i].size(); j++) {
					if (j != res[i].size() - 1)
						cout << res[i][j].orSe << " ";
					else
						cout << res[i][j].orSe << endl;
				}
			}
			else cout << endl;
		}
	}
}

    发表于 2020-04-04 15:24:23 回复(0)
    C/C++
    Dancer_Wu头像 Dancer_Wu
    竟然不保护第一志愿，好尴尬。。。。 
    #include<iostream>
(720)#include<vector>
#include<string>
(765)#include<algorithm>
using namespace std;
struct stuinfor
{
	int no;
	int GE;
	int GI;
	int total;
	vector<int> choice;
	bool operator<(stuinfor c)
	{
		if (total == c.total) return GE > c.GE;
		return total > c.total;
	}
};
bool Comp(stuinfor a,stuinfor b)
{
	return a.no < b.no;
}
int main()           
{       
	int stucount;      //学生总数
	int schoolcount;    //学习数
	int k;    //报考学校数
	while (cin>>stucount>>schoolcount>>k)
	{
		vector<int> schoolstcount;      //学校招生数
		vector<stuinfor> schoolhad[50];      //学校录取
		vector<stuinfor> cons;          
		for (int i = 0; i < schoolcount; i++)
		{   
			int a;
			cin >> a;
			schoolstcount.push_back(a);
		}
		for (int i = 0; i < stucount; i++)
		{
			stuinfor z;
			z.no = i;
			cin >> z.GE >> z.GI;
			z.total = z.GE + z.GI;
			for (int j = 0; j < k; j++)
			{
				int a;
				cin >> a;
				z.choice.push_back(a);

			}
			cons.push_back(z);
		}
		sort(cons.begin(), cons.end());
		for (int i = 0; i < cons.size(); i++)
		{
			for (int j = 0; j < cons[i].choice.size(); j++)
			{ 
				int no = cons[i].choice[j];
				if (schoolstcount[no] > 0)
				{
					schoolhad[no].push_back(cons[i]);
					schoolstcount[no]--;
					break;
				}
				else if (schoolstcount[no] == 0)
				{
					if (schoolhad[no].size() != 0)
					{
						int n=schoolhad[no].size()-1;
						if (schoolhad[no][n].total == cons[i].total&&schoolhad[no][n].GE == cons[i].GE)
						{
							schoolhad[no].push_back(cons[i]);
							break;
						}
					}
				
				
				}
			
			
			
			}
		
		}
		for (int i = 0; i < schoolcount; i++)
			sort(schoolhad[i].begin(), schoolhad[i].end(),Comp);
		for (int i = 0; i < schoolcount; i++)
		{
			for (int j = 0; j < schoolhad[i].size(); j++)
				if (j == 0) cout << schoolhad[i][j].no;
				 else cout <<" "<< schoolhad[i][j].no ;
			cout << endl;
		
		
		}


	
	}





}


    发表于 2020-03-28 19:48:40 回复(0)
    牛客154976338号头像 牛客154976338号
    这个题让我对人生产生了怀疑，学校录取不是按志愿顺序录取的吗?第一志愿录取不满再录取第二志愿，这个题是竟是按分数录取，学校不分志愿。
    发表于 2020-03-09 18:12:04 回复(0)
    C/C++
    Mike尼头像 Mike尼 
    #include <bits/stdc++.h>
using namespace std;
int n,m,k,quato[105],choose[40005][5];
vector<int> admitted[105];
struct adm{
    int id,ge,gi,ga;
}adlis[40005],mp[40005];
auto cmp = [](adm &a,adm &b){return a.ga == b.ga ? a.ge >b.ge : a.ga > b.ga;};
int main(){
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 0;i < m;i++) scanf("%d",&quato[i]);
    for(int i = 0;i < n;i++){
        scanf("%d %d",&adlis[i].ge,&adlis[i].gi);
        adlis[i].id = i,adlis[i].ga = adlis[i].ge + adlis[i].gi;
        mp[i] = adlis[i];
        for(int j = 0;j < k;j++) scanf("%d",&choose[i][j]);
    }
    sort(adlis,adlis+n,cmp);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < k;j++){
            int scid = choose[adlis[i].id][j],lastId = admitted[scid].empty() ? -1 : admitted[scid].back();
            if(quato[scid] > 0 || (adlis[i].ga == mp[lastId].ga && adlis[i].ge == mp[lastId].ge)){
                admitted[scid].push_back(adlis[i].id);
                quato[scid]--;
                break;
            }
        }
    }
    for(int i = 0;i < m;i++){
        if(!admitted[i].empty()){
            sort(admitted[i].begin(),admitted[i].end());
            int size = admitted[i].size();
            printf("%d",admitted[i].front());
            for(int j = 1;j < size;j++) printf(" %d",admitted[i][j]);
        }
        printf("\n");
    }
    return 0;
}
    发表于 2020-02-10 17:10:51 回复(0)
    C/C++
    机器也学不会头像 机器也学不会
    用vector<stu> school[i]表示学校i的录取名单。先将每位学生按给定要求排序，确定每个学生的排名。然后按分数从高到底考虑每个学生，依次考察其每个志愿，如果该志愿( 假设是i )学校还有名额，就将这个学生结点加入到school[i]中。如果没有余额，则遍历school[i]看有没有和当前学生排名相同的，如果有则破额录取。最后将school[i]从i=0~n-1，按学生编号排序并输出编号 
    #include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=40005;
struct stu
{
	int no,ge,gi,g,rank,c[5];
}r[maxn];
bool cmp1(stu a,stu b)
{
	if(a.g!=b.g)	return a.g>b.g;
	else  return a.ge>b.ge;
}
bool cmp2(stu a,stu b)
{
	return a.no<b.no;
}
vector<stu> school[105];
int main()
{
	int n,m,k,quota[105];
	cin>>n>>m>>k;
	for(int i=0;i<m;++i)
		cin>>quota[i];
	for(int i=0;i<n;++i)
	{
		r[i].no=i;
		cin>>r[i].ge>>r[i].gi;
		r[i].g=r[i].ge+r[i].gi;
		for(int j=0;j<k;++j)
			cin>>r[i].c[j];
	}
	sort(r,r+n,cmp1);
	r[0].rank=1;
	for(int i=1;i<n;++i)
		if(r[i].g==r[i-1].g&&r[i].ge==r[i-1].ge)	r[i].rank=r[i-1].rank;
		else  r[i].rank=i+1;
	
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<k;++j)
		{
			int x=r[i].c[j];
			if(quota[x]>0)
			{
				quota[x]--;
				school[x].push_back(r[i]);
				break;
			}
			else
			{
				int flag=0;
				for (auto it=school[x].begin();it!=school[x].end();++it)
				{
					if((*it).rank==r[i].rank)
					{
						flag=1;
						break;
					}
				}
				if(flag)
				{
					quota[x]--;
					school[x].push_back(r[i]);
					break;
				}
			}
		}
	}
	for(int i=0;i<m;++i)
	{
		sort(school[i].begin(),school[i].end(),cmp2);
		for(auto it=school[i].begin();it!=school[i].end();++it)
			cout<<(*it).no<<" ";
		cout<<endl;
	}
	return 0;
}


    编辑于 2020-01-16 09:20:02 回复(0)
    月下2015头像 月下2015 
    line = input().split()
 N ,M, k= int(line[0]),int(line[1]),int(line[2])
 admit_num =[int(i) for i in input().split()]
 students = [[] for i in range(N)]
 schools = [[] for i in range(M)]
 for i in range(N):
 students[i] = [int(stu) for stu in input().split()]
 students[i].append(i)
 students[i].append((students[i][0]+students[i][1])/2)
 sort_students = sorted(students,key = lambda x:(x[-1],x[0]),reverse = True)
 for stu in sort_students:
 for j in range(k):
 if len(schools[stu[j+2]]) < admit_num[stu[j+2]]:
 schools[stu[j+2]].append(stu[-2])
 break
 else:
 final_num = schools[stu[j+2]][-1]
 if stu[-1] == students[final_num][-1] and stu[0] == students[final_num][0]:
 schools[stu[j+2]].append(stu[-2])
 break
 for k in range(M):
 schools[k] = sorted(schools[k])
 print(" ".join(str(i) for i in schools[k]))

    编辑于 2018-10-30 17:50:17 回复(0)
    samer头像 samer
    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>

    typedef struct score_node
    {
        int g1;
        int g2;
        int num;
        int *choice;
        struct score_node* next;
    }node;


    int main()
    {
        int n,m,k;
        int school_limit[100];
        int pre_admit[100];
        int admitted[40000];
        while(scanf("%d%d%d",&n,&m,&k)!=EOF){
            memset(school_limit,0,100);
            for(int i=0;i<40000;i++){
                admitted[i]=-1;
            }
            for(int i=0;i<m;i++){
                scanf("%d",school_limit+i);
            }
            node **app;
            app=(node **)malloc(sizeof(node *)*201);
            for(int i=0;i<201;i++){
                app[i]=(node *)malloc(sizeof(node));
                app[i]->next=NULL;
                app[i]->g1=INT_MAX;
            }
            for(int i=0;i<n;i++){
                int g1,g2,num;
                num=i;
                scanf("%d%d",&g1,&g2);
                node *tmp=(node *)malloc(sizeof(node));
                tmp->g1=g1;
                tmp->g2=g2;
                tmp->num=num;
                tmp->next=NULL;
                tmp->choice=(int *)malloc(sizeof(int)*k);
                for(int j=0;j<k;j++){
                    scanf("%d",&tmp->choice[j]);
                }
                
                int rank=g1+g2;
                node *head=app[rank];
                while(head->next!=NULL && (head->next->g1)>g1) head=head->next;
                if(head->next!=NULL){
                    tmp->next=head->next;
                    head->next=tmp;
                }
                else{
                    head->next=tmp;
                }
            }
            for(int i=200;i>-1;i--){
                node *tmp=app[i];
                int pre_g1=-1,pre_g2=-1,pre_admitted=0,pre_choice=-1;
                if(tmp->next==NULL) continue;
                tmp=tmp->next;
                while(tmp){
                    if(tmp->g1!=pre_g1 || tmp->g2!=pre_g2){
                        for(int i=0;i<m;i++){
                            pre_admit[i]=-1;
                        }
                    }
                    for(int j=0;j<k;j++){
                        if(school_limit[tmp->choice[j]]>0){
                            admitted[tmp->num]=tmp->choice[j];
                            school_limit[tmp->choice[j]]--;
                            pre_admitted=1;
                            pre_choice=tmp->choice[j];
                            pre_g1=tmp->g1;
                            pre_g2=tmp->g2;
                            pre_admit[tmp->choice[j]]=1;
                            break;
                        }
                        else{
                            if(tmp->g1==pre_g1 && tmp->g2==pre_g2 && pre_admitted==1 && pre_admit[tmp->choice[j]]==1){
                                admitted[tmp->num]=tmp->choice[j];
                                school_limit[tmp->choice[j]]--;
                                pre_admitted=1;
                                pre_choice=tmp->choice[j];
                                break;
                            }
                        }
                    }
                    tmp=tmp->next;
                }
                
            }
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(admitted[j]==i) printf("%d ",j);
                }
                printf("\n");
            }
        }
    }
    发表于 2018-09-06 22:51:23 回复(0)
    小猪加油头像 小猪加油 
    #include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct node
{
    int no;
    int ge;
    int gi;
    int fi;
    int will[5];
};

int max_num(int x,int y)
{
    return (x>y)?x:y;
}

int cmp(const void *a,const void *b)
{
    struct node *aa=(struct node *)a;
    struct node *bb=(struct node *)b;
    if(aa->fi!=bb->fi)
        return bb->fi-aa->fi;
    else if(aa->ge!=bb->ge)
        return bb->ge-aa->ge;
    else
        return 0;
}

int cmp2(const void *a,const void *b)
{
    struct node *aa=(struct node *)a;
    struct node *bb=(struct node *)b;
    if(aa->will[0]!=bb->will[0])
        return aa->will[0]-bb->will[0];
    else
        return aa->no-bb->no;
}

struct node buf[40000];
int school[100];

int main(void)
{
    int x,i,j,n,m,limi,big;
    int school_big,will_big;
    while(~scanf("%d %d %d",&big,&school_big,&will_big))
    {
        for(i=0;i<school_big;i++)
            scanf("%d",school+i);
        for(i=0;i<big;i++)
        {
            buf[i].no=i;
            scanf("%d %d",&(buf[i].ge),&(buf[i].gi));
            buf[i].fi=buf[i].ge+buf[i].gi;
            for(j=0;j<will_big;j++)
                scanf("%d",&(buf[i].will[j]));
        }
        qsort(buf,big,sizeof(struct node),cmp);
        for(i=0;i<big;i++)
        {
            for(j=0;j<will_big;j++)
            {
                x=buf[i].will[j];
                if(school[x]>0)
                {
                    buf[i].will[0]=x;
                    school[x]--;
                    break;
                }
            }
            if(j==will_big)
                buf[i].will[0]=128;
        }
        qsort(buf,big,sizeof(struct node),cmp2);
        for(i=0;i<school_big;i++)
        {
            for(j=0;;j++)
            {
                x=buf[j].will[0];
                if(x<i)
                    continue;
                else if(x==i)
                    printf("%d",buf[j].no);
                if(j==big||buf[j+1].will[0]>i)
                {
                    printf("\n");
                    break;
                }
                else
                    printf(" ");
            }
        }
    }
}
    卡在90.90%了，有高手帮忙康康吗
    发表于 2018-09-03 09:47:24 回复(1)
    提交观点

    问题信息

    排序
    难度：
    20条回答 5507浏览

    热门推荐

    通过挑战的用户

    查看代码

    相关试题

    Graduate Admission

    扫一扫，把题目装进口袋

    求职之前，先上牛客

    扫描二维码，进入QQ群

    扫描二维码，关注牛客公众号