奥运排序问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3989 Accepted Submission(s): 1050
Problem Description
按要求，给国家进行排名。
Input
有多组数据。
第一行给出国家数N，要求排名的国家数M，国家号从0到N-1。
第二行开始的N行给定国家或地区的奥运金牌数，奖牌数，人口数（百万）。
接下来一行给出M个国家号。
Output
排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例
对每个国家给出最佳排名排名方式 和 最终排名
格式为: 排名:排名方式
如果有相同的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例
如果有并列排名的情况，即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4.
每组数据后加一个空行。
Sample Input
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
Sample Output
1:3
1:1
2:1
1:2
1:1
1:1
Source
浙大计算机研究生复试上机考试-2010年
题解
按题意模拟。注意是对给定的编号的国家进行排序。(写了五个cmp也是…)代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
using namespace std ;
typedef struct{
double au_medals ;
double tot_medals ;
double population ;
double number ;
double au_population ;
double tot_population ;
int rank1 ;
int rank2 ;
int rank3 ;
int rank4 ;
int min_rank ;
int best_way ;
}meassage ;
bool cmp( meassage a , meassage b ){
return a.number < b.number ;
}
bool cmp_au( meassage a , meassage b ){
return a.au_medals > b.au_medals ;
}
bool cmp_tot( meassage a , meassage b ){
return a.tot_medals > b.tot_medals ;
}
bool cmp_au_pop( meassage a , meassage b ){
return a.au_population > b.au_population ;
}
bool cmp_tot_pop( meassage a , meassage b ){
return a.tot_population > b.tot_population ;
}
int main(){
int n , m ;
while ( cin >> n >> m ){
meassage meaa[n + 10] ;
for ( int i = 0 ; i < n ; i ++ ){
cin >> meaa[i].au_medals >> meaa[i].tot_medals >> meaa[i].population ;
meaa[i].number = i ;
meaa[i].au_population = meaa[i].au_medals / meaa[i].population ;
meaa[i].tot_population = meaa[i].tot_medals / meaa[i].population ;
}
meassage mea[n + 10] ;
for ( int i = 0 ; i < m ; i ++ ){
int number ;
cin >> number ;
mea[i] = meaa[number] ;
mea[i].number = i ;
}
sort(mea , mea + m , cmp_au) ;
for ( int i = 0 ; i < m ; i ++ ){
mea[i].rank1 = i ;
}
for ( int i = 1 ; i < m ; i ++ ){
if ( mea[i].au_medals == mea[i-1].au_medals ){
mea[i].rank1 = mea[i-1].rank1 ;
}
}
sort(mea , mea + m , cmp_tot) ;
for ( int i = 0 ; i < m ; i ++ ){
mea[i].rank2 = i ;
}
for ( int i = 1 ; i < m ; i ++ ){
if ( mea[i].tot_medals == mea[i-1].tot_medals ){
mea[i].rank2 = mea[i-1].rank2 ;
}
}
sort(mea , mea + m , cmp_au_pop) ;
for ( int i = 0 ; i < n ; i ++ ){
mea[i].rank3 = i ;
}
for ( int i = 1 ; i < m ; i ++ ){
if ( mea[i].au_population == mea[i-1].au_population ){
mea[i].rank3 = mea[i-1].rank3 ;
}
}
sort(mea , mea + m , cmp_tot_pop) ;
for ( int i = 0 ; i < m ; i ++ ){
mea[i].rank4 = i ;
}
for ( int i = 1 ; i < m ; i ++ ){
if ( mea[i].tot_population == mea[i-1].tot_population ){
mea[i].rank4 = mea[i-1].rank4 ;
}
}
sort(mea , mea + m , cmp) ;
for ( int i = 0 ; i < m ; i ++ ){
int min_rank = mea[i].rank1 ;
mea[i].best_way = 1 ;
if ( mea[i].rank2 < min_rank ){
min_rank = mea[i].rank2 ;
mea[i].best_way = 2 ;
}
if ( mea[i].rank3 < min_rank ){
min_rank = mea[i].rank3 ;
mea[i].best_way = 3 ;
}
if ( mea[i].rank4 < min_rank ){
min_rank = mea[i].rank4 ;
mea[i].best_way = 4 ;
}
printf("%d:%d\n" , min_rank + 1 , mea[i].best_way) ;
}
puts("") ;
}
return 0 ;
}