1400 - 奥运排序问题
按要求，给国家进行排名。
题目输入
有多组数据。
第一行给出国家数N，要求排名的国家数M，国家号从0到N-1。
第二行开始的N行给定国家或地区的奥运金牌数，奖牌数，人口数（百万）。
接下来一行给出M个国家号。
题目输出
排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例
对每个国家给出最佳排名排名方式 和 最终排名
格式为: 排名:排名方式
如果有相同的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例
如果有并列排名的情况，即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4.
每组数据后加一个空行。
输入/输出样例
题目输入
4 4 4 8 1 6 6 2 4 8 2 2 12 4 0 1 2 3 4 2 8 10 1 8 11 2 8 12 3 8 13 4 0 3
题目输出
1:3 1:1 2:1 1:2 1:1 1:1
提示
本题需要解决的是奥运会中各国家最有利的排名方式以及名次。只要进行五次排序即可。首先读入各国家信息，写好国家编号，计算和存储排名所需要的数据。然后按四种排名方式分别对需要排名的国家进行排名，并记录名次。最后使用国家编号对国家进行排名。这样就可以输出结果了。
C语言解答
#include <stdio.h> #include <malloc.h> typedef struct Record { int gold; int award; int people; }Record; int sort(Record *recs,int nums[],int M) { for(int i=0;i<M;i++) { int rank[4]; rank[0]=M; rank[1]=M; rank[2]=M; rank[3]=M; for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).gold>=(*(recs+nums[j])).gold) { rank[0]--; } } for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).award>=(*(recs+nums[j])).award) { rank[1]--; } } for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).gold/(float)((*(recs+nums[i])).people)>=(*(recs+nums[j])).gold/(float)((*(recs+nums[j])).people)) { rank[2]--; } } for(int j=0;j<M;j++) { if(i!=j&&(*(recs+nums[i])).gold/(float)((*(recs+nums[i])).people)>=(*(recs+nums[j])).gold/(float)((*(recs+nums[j])).people)) { rank[3]--; } } int min=rank[0];int minp=0; for(int i=1;i<4;i++) { if(min>rank[i]) { min=rank[i]; minp=i; } } printf("%d:%d\n",min,minp+1); } printf("\n"); } int main() { while(1) { int N; int M; int nums[200]; if(scanf("%d",&N)==EOF) { break; } scanf("%d",&M); Record* recs=(Record*)malloc(N*sizeof(Record)); for(int i=0;i<N;i++) { scanf("%d",&((*(recs+i)).gold)); scanf("%d",&((*(recs+i)).award)); scanf("%d",&((*(recs+i)).people)); } for(int i=0;i<M;i++) { scanf("%d",&nums[i]); } sort(recs,nums,M); } }
C++解答
#include <stdio.h> #include <algorithm> using namespace std; struct Nation{ // 国家信息结构类型 int num; // 国家编号 double orderValue[4]; // 用来排名的值 int order[4]; // 名次 }; Nation na[100000]; // 存储国家信息 bool cmp0(Nation a,Nation b){ // 按国家编号排名 return a.num < b.num; } bool cmp1(Nation a,Nation b){ // 按金牌数排名 return a.orderValue[0] > b.orderValue[0]; } bool cmp2(Nation a,Nation b){ // 按奖牌数排名 return a.orderValue[1] > b.orderValue[1]; } bool cmp3(Nation a,Nation b){ // 按金牌人口比排名 return a.orderValue[2] > b.orderValue[2]; } bool cmp4(Nation a,Nation b){ // 按奖牌人口比排名 return a.orderValue[3] > b.orderValue[3]; } int main(){ #ifndef ONLINE_JUDGE freopen("in", "r", stdin); #endif int n, m; // 用来存储国家总数以及需要排名国家的数目 int gold, total, pop; // 用来读取金牌数、奖牌数以及人口 int need; // 存储需要排名的国家编号数 while(scanf("%d%d", &n, &m) != EOF){ int i; for(i=0; i<n; i++){ // 读入国家信息，并计算金牌人口比以及奖牌人口比 scanf("%d%d%d", &gold, &total, &pop); na[i].orderValue[0] = gold; na[i].orderValue[1] = total; na[i].orderValue[2] = 1.0*gold/pop; na[i].orderValue[3] = 1.0*total/pop; na[i].num = i; } for(i=0; i<m; i++){ // 只存储需要排名的国家 scanf("%d", &need); na[i] = na[need]; } // 按金牌数排名，计算名次 sort(na, na+m, cmp1); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[0]==na[i].orderValue[0]){ na[i].order[0] = na[i-1].order[0]; }else{ na[i].order[0] = i+1; } } // 按奖牌数排名，计算名次 sort(na, na+m, cmp2); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[1]==na[i].orderValue[1]){ na[i].order[1] = na[i-1].order[1]; }else{ na[i].order[1] = i+1; } } // 按金牌人口比排名，计算名次 sort(na, na+m, cmp3); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[2]==na[i].orderValue[2]){ na[i].order[2] = na[i-1].order[2]; }else{ na[i].order[2] = i+1; } } // 按奖牌人口比排名，计算名次 sort(na, na+m, cmp4); for(i=0; i<m; i++){ if(i>0 && na[i-1].orderValue[3]==na[i].orderValue[3]){ na[i].order[3] = na[i-1].order[3]; }else{ na[i].order[3] = i+1; } } // 按国家编号排序，输出结果 sort(na, na+m, cmp0); int j, index; for(i=0; i<m; i++){ index = 0; // 从四种方法中获得最佳结果 for(j=0; j<4; j++){ if(na[i].order[j] < na[i].order[index]){ index = j; } } printf("%d:%d\n", na[i].order[index], index+1); } putchar('\n'); } return 0; }
提示
本题需要解决的是奥运会中各国家最有利的排名方式以及名次。只要进行五次排序即可。首先读入各国家信息，写好国家编号，计算和存储排名所需要的数据。然后按四种排名方式分别对需要排名的国家进行排名，并记录名次。最后使用国家编号对国家进行排名。这样就可以输出结果了。