题解 | #奥运排序问题#

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

/*
 * 国家
 */
struct Country {
    int goldMedal;      //金牌数
    int medal;          //奖牌总数
    int population;     //人口
    int initOrder;      //国家号
    int goldMedalRank;  //
    int medalRank;
    int ratio4GoldMedalAndPopulationRank;
    int ratio4MedalAndPopulationRank;
};

/**
 * 金牌总数排序
 * @param x
 * @param y
 * @return
 */
bool compareByGoldMedal(Country x, Country y) {
    return x.goldMedal > y.goldMedal;
}

/**
 * 奖牌总数排序
 * @param x
 * @param y
 * @return
 */
bool compareByMedal(Country x, Country y) {
    return x.medal > y.medal;
}

/**
 * 金牌人口比例排序
 * @param x
 * @param y
 * @return
 */
bool compareByRatio4GoldMedalAndPopulation(Country x, Country y) {
    double xRatio = x.goldMedal * 1.0 / x.population;
    double yRatio = y.goldMedal * 1.0 / y.population;
    return xRatio > yRatio;
}

/**
 * 奖牌人口排序
 * @param x
 * @param y
 * @return
 */
bool compareByRatio4MedalAndPopulation(Country x, Country y) {
    double xRatio = x.medal * 1.0 / x.population;
    double yRatio = y.medal * 1.0 / y.population;
    return xRatio > yRatio;
}

/**
 * 按初始顺序排序
 * @param x
 * @param y
 * @return
 */
bool compareByInitOrder(Country x, Country y) {
    return x.initOrder < y.initOrder;
}

/**
 * 奥运排序问题--北京大学
 * @return
 */
int main() {
    int n;      //国家数
    int m;      //要求排名的国家树
    while (cin >> n >> m) {


        Country* country = new Country[n];
        for (int i = 0; i < n; ++i) {
            country[i].initOrder = i;
            cin >> country[i].goldMedal >> country[i].medal >> country[i].population;
        }

        int* waitSort = new int[m];
        for (int j = 0; j < m; ++j) {
            cin >> waitSort[j];
        }


        /*
         * 对金牌数进行排序
         */
        sort(country, country + n, compareByGoldMedal);
        //排序后的第一个排名就是1
        country[0].goldMedalRank = 1;
        for (int i = 1; i < n; ++i) {
            if (country[i - 1].goldMedal == country[i].goldMedal) {
                //金牌总数相同，则排名相同
                country[i].goldMedalRank = country[i - 1].goldMedalRank;
            } else {
                //金牌总数不同，则排名变为 i+1
                country[i].goldMedalRank = i + 1;
            }
        }

        /*
         * 对奖牌总数进行排序
         */
        sort(country, country + n, compareByMedal);
        country[0].medalRank = 1;
        for (int i = 0; i < n; ++i) {
            if (country[i - 1].medal == country[i].medal) {
                country[i].medalRank = country[i - 1].medalRank;
            } else {
                country[i].medalRank = i + 1;
            }
        }

        /*
         * 对金牌人口比例进行排序
         */
        sort(country, country + n, compareByRatio4GoldMedalAndPopulation);
        country[0].ratio4GoldMedalAndPopulationRank = 1;
        for (int i = 0; i < n; ++i) {
            if (1.0 * country[i].goldMedal / country[i].population ==
                    1.0 * country[i - 1].goldMedal / country[i - 1].population) {
                country[i].ratio4GoldMedalAndPopulationRank = country[i -
                        1].ratio4GoldMedalAndPopulationRank;
            } else {
                country[i].ratio4GoldMedalAndPopulationRank = i + 1;
            }
        }

        /*
         * 对奖牌人口比例进行排序
         */
        sort(country, country + n, compareByRatio4MedalAndPopulation);
        country[0].ratio4MedalAndPopulationRank = 1;
        for (int i = 0; i < n; ++i) {
            if (1.0 * country[i].medal / country[i].population ==
                    1.0 * country[i - 1].medal / country[i - 1].population) {
                country[i].ratio4MedalAndPopulationRank = country[i -
                        1].ratio4MedalAndPopulationRank;
            } else {
                country[i].ratio4MedalAndPopulationRank = i + 1;
            }
        }

        /*
         * 将序列按initOrder排序，即回归原本的序列
         * 输出需要排序的国家
         * 输出四种排名中最小的一个
         */
        sort(country, country + n, compareByInitOrder);
        for (int i = 0; i < m; ++i) {
            int index = waitSort[i];
            Country cur = country[index];
            int r1 = cur.goldMedalRank;
            int r2 = cur.medalRank;
            int r3 = cur.ratio4GoldMedalAndPopulationRank;
            int r4 = cur.ratio4MedalAndPopulationRank;
            if (r1 <= r2 && r1 <= r3 && r1 <= r4) {
                cout << r1 << ":" << 1 << endl;
            } else if (r2 <= r3 && r2 <= r4 && r2 <= r1) {
                cout << r2 << ":" << 2 << endl;
            } else if (r3 <= r4 && r3 <= r2 && r3 <= r1) {
                cout << r3 << ":" << 3 << endl;
            } else {
                cout << r4 << ":" << 4 << endl;
            }
        }
        cout << endl;
    }

    return 0;
}