7-2 奥运排行榜(PTA - 数据结构)

每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”；而美国的奖牌总数第一，于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”，说不定非洲的国家会成为榜魁…… 现在就请你写一个程序，对每个前来咨询的国家按照对其最有利的方式计算它的排名。

输入格式:

输入的第一行给出两个正整数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;
}