九度 1007 奥运排序有关问题

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：2972

解决：618

题目描述：

按要求，给国家进行排名。

输入：

//如果有相同的最终排名，则输出排名方式最小的那种排名，//对于排名方式，金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例//意思是 所有国家按四种方式分别排序后 ，其中的n（1,2,3,4）种排名相同，取排名方式小的那种排名 for从小的方式开始输出就可以了//注意：最后输入的排序国家号不一定是有序的//思路：把需要排序的国家按四种方式分别排序，计算出每个方式下的排名，输出每个国家四种排序//方式下的最大排名（1>2>3……>n）,如果有相同的排名，则输出排名方式最小的那个排名#include <stdio.h>#include <stdlib.h>#include <math.h>const int MAX_SIZE=1000;struct Country { int iCountryId; //输入时的国家号 不能用下标 排序后就变了 int dGold; //金牌总数 int dPrize; //奖牌总数 int dPopulation; //人口数 double dGoldRatio; // 金牌人口比 double dPrizeRatio;// 奖牌人口比} Countrys[MAX_SIZE],RankCountrys[MAX_SIZE];struct Rank { int iCountryId; int iRank;} Ranks[4][MAX_SIZE]; //四种排名方式下的排名int cmp1(const void *a,const void *b);int cmp2(const void *a,const void *b);int cmp3(const void *a,const void *b);int cmp4(const void *a,const void *b);int main(){ int n,m,i,j,k,Id,RankCountryId[MAX_SIZE];//国家数 要求排名的国家数 要排名的国家号 while(scanf("%d%d",&n,&m)!=EOF) { for(i=0; i<n; i++) { scanf("%d%d%d",&Countrys[i].dGold,&Countrys[i].dPrize,&Countrys[i].dPopulation); Countrys[i].dGoldRatio=(double)Countrys[i].dGold/Countrys[i].dPopulation; Countrys[i].dPrizeRatio=(double)Countrys[i].dPrize/Countrys[i].dPopulation; Countrys[i].iCountryId=i; } for(i=0; i<m; i++) { //筛选需要排序的国家 scanf("%d",&Id); RankCountryId[i]=Id;//记下需要排序的国家号 RankCountrys[i]=Countrys[Id]; } //按金牌排序 qsort(RankCountrys,m,sizeof(Country),cmp1); Ranks[0][0].iCountryId=RankCountrys[0].iCountryId; Ranks[0][0].iRank=1; for(i=1; i<m; i++) { Ranks[0][i].iCountryId=RankCountrys[i].iCountryId; if(RankCountrys[i-1].dGold==RankCountrys[i].dGold) Ranks[0][i].iRank=Ranks[0][i-1].iRank;//并列排名 else Ranks[0][i].iRank=i+1; //实际排名 } //按奖牌排序 qsort(RankCountrys,m,sizeof(Country),cmp2); Ranks[1][0].iCountryId=RankCountrys[0].iCountryId; Ranks[1][0].iRank=1; for(i=1; i<m; i++) { Ranks[1][i].iCountryId=RankCountrys[i].iCountryId; if(RankCountrys[i-1].dPrize==RankCountrys[i].dPrize) Ranks[1][i].iRank=Ranks[1][i-1].iRank; else Ranks[1][i].iRank=i+1; } //按金牌人口比排序 qsort(RankCountrys,m,sizeof(Country),cmp3); Ranks[2][0].iCountryId=RankCountrys[0].iCountryId; Ranks[2][0].iRank=1; for(i=1; i<m; i++) { Ranks[2][i].iCountryId=RankCountrys[i].iCountryId; if(RankCountrys[i].dGoldRatio==RankCountrys[i-1].dGoldRatio) Ranks[2][i].iRank=Ranks[2][i-1].iRank; else Ranks[2][i].iRank=i+1; } //按奖牌人口比排序 qsort(RankCountrys,m,sizeof(Country),cmp4); Ranks[3][0].iCountryId=RankCountrys[0].iCountryId; Ranks[3][0].iRank=1; for(i=1; i<m; i++) { Ranks[3][i].iCountryId=RankCountrys[i].iCountryId; if(RankCountrys[i].dPrizeRatio==RankCountrys[i-1].dPrizeRatio) Ranks[3][i].iRank=Ranks[3][i-1].iRank; else Ranks[3][i].iRank=i+1; } //找出最佳排序方式输出 必须遍历每种排名中的每个元素 不然会漏掉 int rank,way; bool first; for(i=0; i<m; i++) { first=true; for(j=0; j<4; j++) for(k=0; k<m; k++) { if(Ranks[j][k].iCountryId==RankCountryId[i]) { if(first) { rank=Ranks[j][k].iRank; way=j; first=false; } else { if(Ranks[j][k].iRank<rank) { rank=Ranks[j][k].iRank; way=j; } } } } printf("%d:%d\n",rank,way+1); } printf("\n"); } return 0;}//按金牌数排序 降序int cmp1(const void *a,const void *b){ Country *c1=(Country*)a; Country *c2=(Country*)b; return c2->dGold- c1->dGold;}//按奖牌数排序int cmp2(const void *a,const void *b){ Country *c1=(Country*)a; Country *c2=(Country*)b; return c2->dPrize -c1->dPrize;}//按金牌人口比排序int cmp3(const void *a,const void *b){ Country *c1=(Country*)a; Country *c2=(Country*)b; return c2->dGoldRatio > c1->dGoldRatio ? 1:-1;}//按奖牌人口比排序int cmp4(const void *a,const void *b){ Country *c1=(Country*)a; Country *c2=(Country*)b; return c2->dPrizeRatio > c1->dPrizeRatio ? 1:-1;}/************************************************************** Problem: 1007 User: windzhu Language: C++ Result: Accepted Time:10 ms Memory:1108 kb****************************************************************/