九度oj 题目1007:奥运排序问题 恢复
题目描述:
-
按要求,给国家进行排名。
- 输入:
-
有多组数据。 第一行给出国家数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 这道题不难,但我也提交了N次才通过,悲哀 原先的代码是这样1 #include <cstdio>
2 #include <cstdlib>
3 #include <cstring>
4 #include <string>
5 #include <algorithm>
6 #define MAX 1000
7 #define BASIC 1
8 struct country{
9 int goldNum;
10 int medalNum;
11 int population;
12 double goldRatio;
13 double medalRatio;
14 int placeGold;
15 int placeMedal;
16 int placeGR;
17 int placeMR;
18 int num;
19 };
20 country old[MAX];
21 country cal[MAX];
22
23 int compareGOLD(const void* a, const void *b) {
24 return (*(country*)b).goldNum - (*(country*)a).goldNum;
25 }
26
27 int compareMEDAL(const void* a, const void *b) {
28 return (*(country*)b).medalNum - (*(country*)a).medalNum;
29 }
30 int comparegoldRatio(const void* a, const void *b) {
31 return (*(country*)b).goldRatio - (*(country*)a).goldRatio;
32 }
33 int comparemedalRatio(const void* a, const void *b) {
34 return (*(country*)b).medalRatio - (*(country*)a).medalRatio;
35 }
36
37 int compareNum(const void* a, const void *b) {
38 return (*(country*)a).num - (*(country*)b).num;
39 }
40
41 int main(int argc, char const *argv[])
42 {
43 int N,M;
44 //freopen("input.txt","r",stdin);
45 while(scanf("%d %d",&N,&M) != EOF) {
46 for(int i = 0; i < N; i++) {
47 scanf("%d %d %d",&old[i].goldNum,&old[i].medalNum,&old[i].population);
48 }
49 for(int i = 0; i < M; i++) {
50 int toCal;
51 scanf("%d",&toCal);
52 cal[i] = old[toCal];
53 cal[i].goldRatio = (double)cal[i].goldNum/(double)cal[i].population;
54 cal[i].medalRatio = (double)cal[i].medalRatio/(double)cal[i].population;
55 cal[i].placeGold = cal[i].placeMedal = cal[i].placeGR = cal[i].placeMR = -1;
56 cal[i].num = i;
57 }
58 qsort(cal,M,sizeof(country),compareGOLD);
59 int place = 1;
60 cal[0].placeGold = 1;
61 for(int i = 1; i < M; i++) {
62 if(cal[i].goldNum != cal[i-1].goldNum) {
63 place++;
64 }
65 cal[i].placeGold = place;
66 }
67
68
69
70 qsort(cal,M,sizeof(country),compareMEDAL);
71 place = 1;
72 cal[0].placeMedal = 1;
73 for(int i = 1; i < M; i++) {
74 if(cal[i].medalNum != cal[i-1].medalNum) {
75 place++;
76 }
77 cal[i].placeMedal = place;
78 }
79
80 qsort(cal,M,sizeof(country),comparegoldRatio);
81 place = 1;
82 cal[0].placeGR = 1;
83 for(int i = 1; i < M; i++) {
84 if(cal[i].goldRatio != cal[i-1].goldRatio) {
85 place++;
86 }
87 cal[i].placeGR = place;
88 }
89
90 qsort(cal,M,sizeof(country),comparemedalRatio);
91 place = 1;
92 cal[0].placeMR = 1;
93 for(int i = 1; i < M; i++) {
94 if(cal[i].placeMR != cal[i-1].placeMR) {
95 place++;
96 }
97 cal[i].placeMR = place;
98 }
99
100 qsort(cal,M,sizeof(country),compareNum);
101 for(int i = 0; i < M; i++) {
102 int min = cal[i].placeGold;
103 int way = BASIC;
104 if(cal[i].placeMedal < min) {
105 min = cal[i].placeMedal;
106 way = BASIC + 1;
107 }
108 if(cal[i].placeGR< min) {
109 min = cal[i].placeGR;
110 way = BASIC + 2;
111 }
112 if(cal[i].placeMR< min) {
113 min = cal[i].placeMR;
114 way = BASIC + 3;
115 }
116 printf("%d:%d\n",min,way);
117 }
118 printf("\n");
119
120 /*for(int i = 0; i < M; i++) {
121
122 printf("%d %d %d\n",cal[i].num,cal[i].goldNum,cal[i].placeGold);
123 }
124 printf("\n");*/
125 }
126 return 0;
127 }这段代码犯了两个错误,一是54行粗心的把medalRatio算错,二是计算排名时算错,按照题目要求,如果有并列排名的情况,即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4. 而我的程序写出来则是1,2,2,3 改正后的代码如下:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#define MAX 1005
#define BASIC 1
struct country{
int goldNum;
int medalNum;
int population;
double goldRatio;
double medalRatio;
int placeGold;
int placeMedal;
int placeGR;
int placeMR;
int num;
};
country old[MAX];
country cal[MAX]; int compareGOLD(const void* a, const void *b) {
return (*(country*)b).goldNum - (*(country*)a).goldNum;
} int compareMEDAL(const void* a, const void *b) {
return (*(country*)b).medalNum - (*(country*)a).medalNum;
}
int comparegoldRatio(const void* a, const void *b) {
return (*(country*)b).goldRatio - (*(country*)a).goldRatio;
}
int comparemedalRatio(const void* a, const void *b) {
return (*(country*)b).medalRatio - (*(country*)a).medalRatio;
} int compareNum(const void* a, const void *b) {
return (*(country*)a).num - (*(country*)b).num;
} int main(int argc, char const *argv[])
{
int N,M;
//freopen("input.txt","r",stdin);
while(scanf("%d %d",&N,&M) != EOF) {
for(int i = ; i < N; i++) {
scanf("%d %d %d",&old[i].goldNum,&old[i].medalNum,&old[i].population);
}
for(int i = ; i < M; i++) {
int toCal;
scanf("%d",&toCal);
cal[i] = old[toCal];
cal[i].goldRatio = (double)cal[i].goldNum/(double)cal[i].population;
cal[i].medalRatio = (double)cal[i].medalNum/(double)cal[i].population;
cal[i].placeGold = cal[i].placeMedal = cal[i].placeGR = cal[i].placeMR = MAX;
cal[i].num = i;
}
qsort(cal,M,sizeof(country),compareGOLD); int place = ;
cal[].placeGold = ;
for(int i = ; i < M; i++) {
if(cal[i].goldNum != cal[i-].goldNum) {
place = i+;
} cal[i].placeGold = place;
} /*for(int i = 0; i < M; i++) { printf("%d %d %d\n",cal[i].num,cal[i].goldNum,cal[i].placeGold);
}
printf("\n");*/ qsort(cal,M,sizeof(country),compareMEDAL);
place = ;
cal[].placeMedal = ;
for(int i = ; i < M; i++) {
if(cal[i].medalNum != cal[i-].medalNum) {
place = i+;
} cal[i].placeMedal = place;
} qsort(cal,M,sizeof(country),comparegoldRatio);
place = ;
cal[].placeGR = ;
for(int i = ; i < M; i++) {
if(cal[i].goldRatio != cal[i-].goldRatio) {
place = i+;
} cal[i].placeGR = place;
} qsort(cal,M,sizeof(country),comparemedalRatio);
place = ;
cal[].placeMR = ;
for(int i = ; i < M; i++) {
if(cal[i].placeMR != cal[i-].placeMR) {
place = i+;
} cal[i].placeMR = place;
} qsort(cal,M,sizeof(country),compareNum);
for(int i = ; i < M; i++) {
int min = cal[i].placeGold;
int way = BASIC;
if(cal[i].placeMedal < min) {
min = cal[i].placeMedal;
way = BASIC + ;
}
if(cal[i].placeGR< min) {
min = cal[i].placeGR;
way = BASIC + ;
}
if(cal[i].placeMR< min) {
min = cal[i].placeMR;
way = BASIC + ;
}
printf("%d:%d\n",min,way);
}
printf("\n"); /*printf("M is %d\n",M);
for(int i = 0; i < M; i++) { printf("%d %d %d\n",cal[i].num,cal[i].goldNum,cal[i].placeGold);
}
printf("\n");*/
}
return ;
}多么痛的领悟!