題目1007：奧運排序問題時間限制：1 秒
內存限制：32 兆
特殊判題：否
提交：2972
解決：618
題目描述：
按要求，給國家進行排名。
輸入：
有多組數據。
第一行給出國家數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[cpp]
// ****************************************************************/ //如果有相同的最終排名，則輸出排名方式最小的那種排名，
//對於排名方式，金牌總數 < 獎牌總數 < 金牌人口比例 < 獎牌人口比例
//意思是 所有國家按四種方式分別排序後 ，其中的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
****************************************************************/
