Jobdu 1005-白红宇

Jobdu 1005

阅读量：5171 次

发布时间：2019-06-13

本文共 1863 字，大约阅读时间需要 6 分钟。

地址：

题意：n个学生，m个学校，每个学校q[i]个名额。主旨是学生选学校。每个学生有k个选择，选择优先权是从高到低，每个学生有两个分数ge和gi，如果(ge+gi)/2比较高，则排名　　　　高，如果相等则比较ge，如果仍然相等，则排名相等。学生按照排名先后选择学校，轮到该学生选择学校时，如果当前选择的学校名额已满，就看选择的下一个学校，以此类　　　　推，如果所有学校都满，则无学校可选。特殊情况：当同等排名的学生且选到相同学校，如果该学校名额不够分配给同等排名的学生，会破格录取这些学生。

mark：该题用C++STL的set很方便的解决问题。set的有关说明

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;typedef long long LL;typedef struct{ int num; int ge,gi; int pre[5];}ss;int n,m,k;int q[110];ss s[40010];set
                
                  vv[100];set
                 
                  ::iterator it;bool vst[40010];int cmp(const void *a, const void *b){ ss *aa = (ss *)a, *bb = (ss *)b; if(aa->ge+aa->gi == bb->ge+bb->gi) { if(aa->ge == bb->ge) return aa->num - bb->num; return bb->ge - aa->ge; } return bb->ge+bb->gi-aa->ge-aa->gi;}int main(int argc, char **argv){ int i,j; while(cin >> n >> m >> k) { for(i = 0; i < m; i++) { vv[i].clear(); cin >> q[i]; } for(i = 0; i < n; i++) { s[i].num = i; cin >> s[i].ge >> s[i].gi; for(j = 0; j < k; j++) cin >> s[i].pre[j]; } qsort(s, n, sizeof(ss), cmp); memset(vst, 0, sizeof(vst)); for(i = 0; i < n; i++) { if(vst[i]) continue; for(j = 0; j < k; j++) { if(!q[s[i].pre[j]]) continue; vv[s[i].pre[j]].insert(s[i].num); if(q[s[i].pre[j]] > 1) { q[s[i].pre[j]]--; break; } int p = i+1; while(s[i].ge == s[p].ge && s[i].ge+s[i].gi == s[p].ge+s[p].gi) { for(int x = 0; x < k; x++) { if(!q[s[p].pre[x]]) continue; if(s[p].pre[x] == s[i].pre[j]) { vv[s[i].pre[j]].insert(s[p].num); vst[p] = 1; } else break; } p++; } q[s[i].pre[j]]--; break; } } for(i = 0; i < m; i++) { j = 0; for(it = vv[i].begin(); it != vv[i].end(); it++) { if(j++) cout << ' '; cout << *it; } cout << endl; } } return 0;}

转载于:https://www.cnblogs.com/andre0506/archive/2013/05/27/3102841.html

你可能感兴趣的文章