7-2 奥运排行榜(PTA - 数据结构)
2023-12-22 23:16:15
每年奥运会各大媒体都会公布一个排行榜,但是细心的读者发现,不同国家的排行榜略有不同。比如中国金牌总数列第一的时候,中国媒体就公布“金牌榜”;而美国的奖牌总数第一,于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”,说不定非洲的国家会成为榜魁…… 现在就请你写一个程序,对每个前来咨询的国家按照对其最有利的方式计算它的排名。
输入格式:
输入的第一行给出两个正整数N和M(≤224,因为世界上共有224个国家和地区),分别是参与排名的国家和地区的总个数、以及前来咨询的国家的个数。为简单起见,我们把国家从0 ~?N?1编号。之后有N行输入,第i行给出编号为i?1的国家的金牌数、奖牌数、国民人口数(单位为百万),数字均为[0,1000]区间内的整数,用空格分隔。最后面一行给出M个前来咨询的国家的编号,用空格分隔。
输出格式:
在一行里顺序输出前来咨询的国家的排名:计算方式编号
。其排名按照对该国家最有利的方式计算;计算方式编号为:金牌榜=1,奖牌榜=2,国民人均金牌榜=3,国民人均奖牌榜=4。输出间以空格分隔,输出结尾不能有多余空格。
若某国在不同排名方式下有相同名次,则输出编号最小的计算方式。
输入样例:
4 4
51 100 1000
36 110 300
6 14 32
5 18 40
0 1 2 3
输出样例:
1:1 1:2 1:3 1:4
提交结果:?
思路分析:?
? ? ? ? 排排排,写三个不同判断条件的排序函数。
? ? ? ? 起初我是打算只排一次,然后根据题意找满足题目要求的结果,但是最后2监测点过不去,之后参考了csdn上其他用户的代码,改成每来一个人就重新排序,找它的满足题意的结果。
? ? ? ? 要注意得分并列的情况。
代码:?
//
// Created by DDD on 2023/12/22.
//
#include <stdio.h>
typedef struct {
int Gold;
int Medal;
int Population;
int id;
double GoldAver;
double MedalAver;
}Country;
void Gold_QuickSort(Country array[], int low, int high) { //快排
int i = low;
int j = high;
if(i >= j) {
return;
}
int temp = array[low].Gold;
while(i != j) {
while(array[j].Gold <= temp && i < j) {
j--;
}
while(array[i].Gold >= temp && i < j) {
i++;
}
if(i < j) {
Country tempr = array[j];
array[j] = array[i];
array[i] = tempr;
}
}
Country tempr = array[low];
array[low] = array[i];
array[i] = tempr;
Gold_QuickSort(array, low, i - 1);
Gold_QuickSort(array, i + 1, high);
}
void Medal_QuickSort(Country array[], int low, int high) { //快排
int i = low;
int j = high;
if(i >= j) {
return;
}
int temp = array[low].Medal;
while(i != j) {
while(array[j].Medal <= temp && i < j) {
j--;
}
while(array[i].Medal >= temp && i < j) {
i++;
}
if(i < j) {
Country tempr = array[j];
array[j] = array[i];
array[i] = tempr;
}
}
Country tempr = array[low];
array[low] = array[i];
array[i] = tempr;
Medal_QuickSort(array, low, i - 1);
Medal_QuickSort(array, i + 1, high);
}
void GP_QuickSort(Country array[], int low, int high) { //快排
int i = low;
int j = high;
if(i >= j) {
return;
}
double temp = array[low].GoldAver;
while(i != j) {
while(array[j].GoldAver <= temp && i < j) {
j--;
}
while(array[i].GoldAver >= temp && i < j) {
i++;
}
if(i < j) {
Country tempr = array[j];
array[j] = array[i];
array[i] = tempr;
}
}
Country tempr = array[low];
array[low] = array[i];
array[i] = tempr;
GP_QuickSort(array, low, i - 1);
GP_QuickSort(array, i + 1, high);
}
void MP_QuickSort(Country array[], int low, int high) { //快排
int i = low;
int j = high;
if(i >= j) {
return;
}
double temp = array[low].MedalAver;
while(i != j) {
while(array[j].MedalAver <= temp && i < j) {
j--;
}
while(array[i].MedalAver >= temp && i < j) {
i++;
}
if(i < j) {
Country tempr = array[j];
array[j] = array[i];
array[i] = tempr;
}
}
Country tempr = array[low];
array[low] = array[i];
array[i] = tempr;
MP_QuickSort(array, low, i - 1);
MP_QuickSort(array, i + 1, high);
}
int main(){
int N,M;
scanf("%d %d",&N,&M);
//int flag[4][N];
Country country[N];
for(int i = 0;i<N;i++){
country[i].id = i;
scanf("%d %d %d",&country[i].Gold,&country[i].Medal,&country[i].Population);
if(country[i].Population) {
country[i].GoldAver = 1.0 * country[i].Gold / country[i].Population * 1.0;
country[i].MedalAver = 1.0 * country[i].Medal / country[i].Population * 1.0;
}
else{
country[i].GoldAver = 0;
country[i].MedalAver = 0;
}
}
int x;
for (int i = 0; i < M; ++i) {
scanf("%d",&x);
int rank = 32767;
int way = 0;
Gold_QuickSort(country,0,N-1);
for (int j = 0; j < N; ++j) {
if(x == country[j].id){
while(j!=0 && country[j].Gold == country[j-1].Gold)
j--;
if(j<rank){
rank = j;
way = 1;
}
break;
}
}
Medal_QuickSort(country,0,N-1);
for (int j = 0; j < N; ++j) {
if(x == country[j].id){
while(j!=0 && country[j].Medal == country[j-1].Medal)
j--;
if(j<rank){
rank = j;
way = 2;
}
break;
}
}
GP_QuickSort(country,0,N-1);
for (int j = 0; j < N; ++j) {
if(x == country[j].id){
while(j!=0 && country[j].GoldAver == country[j-1].GoldAver)
j--;
if(j<rank){
rank = j;
way = 3;
}
break;
}
}
MP_QuickSort(country,0,N-1);
for (int j = 0; j < N; ++j) {
if(x == country[j].id){
while(j!=0 && country[j].MedalAver == country[j-1].MedalAver)
j--;
if(j<rank){
rank = j;
way = 4;
}
break;
}
}
if(i == M-1)
printf("%d:%d",rank+1,way);
else printf("%d:%d ",rank+1,way);
}
return 0;
}
文章来源:https://blog.csdn.net/FellAveal/article/details/135161868
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!