奥运排序问题

python写的，花了好几个小时，具体思路还是很清晰的。
按4个关键词进行四次排序
对每次排序的结果进行处理，提取出并列的
再将每个国家的4次排序结果比较，提取出名次最高的
但写起来还是有很多细节的问题，一开始我万万没想到人口还会是0的
在找了半天错之后发现了，然后我将代码修改为当人口为0时用一个极小的人口0.001来代替0，
我原本想的是，不足一百万的极小人口数，结果还是错了。
在多次尝试之后发现，当人口为0时，返回一个极大值100能通过。
原因出在多个人口为0的国家同时出现，举个例子金牌数为9，人口数为0，和金牌数为8，人口数为0。
谁的金牌人口比高？那肯定是9的高，也就是0.001代替0的原因。
但是提交判断的时候这俩国家却是并列第一，虽然不符合常理，当也没有办法，也就是当人口为0时
金牌人口比和奖牌人口比就与金牌数和奖牌数无关，直接为第一。所以用一个极大值100便能通过。
然后还有一个坑就是奖牌数有可能为0，当奖牌和人口同时为0，此时按上面一旦人口为0就是100，
就不对了，两者同时为0时仍应返回0
瞅了下，18ms喜提一个python第一还是蛮开心的。


def by1(set):
    return -set[1][0]
def by2(set):
    return -set[1][1]
def by3(set):  #这题的坑点全在这个函数里了
    if set[1][2]==0:
        if set[1][0] == 0:
            return 0
        return -100
    return -set[1][0]/set[1][2]
def by4(set):
    if set[1][2]==0:
        if set[1][1]==0:
            return 0
        return -100
    return -set[1][1]/set[1][2]

while True:
    try:
        n = input()
        if not n:
            break
        n = n.split()

        N = eval(n[0])
        M = eval(n[1])
        countrys = []
        for i in range(N):
            line = input().split()
            countrys.append((eval(line[0]), eval(line[1]), eval(line[2])))
        line = input().split()
        index = []
        for n in line:
            index.append(eval(n))

        country = []
        order = 0
        for n in index:
            country.append((order, countrys[n]))
            order += 1
        results = [[] for i in range(M)]

        sort1 = [] + country
        sort2 = [] + country
        sort3 = [] + country
        sort4 = [] + country

        sort1.sort(key=by1)
        sort2.sort(key=by2)
        sort3.sort(key=by3)
        sort4.sort(key=by4)

        lastvalue = 1
        rank = 1
        count = 0
        for i in range(M):
            if by1(sort1[i]) == lastvalue:
                count += 1
                results[sort1[i][0]].append(rank)
            else:
                lastvalue = by1(sort1[i])
                rank += count
                results[sort1[i][0]].append(rank)
                count = 1

        lastvalue = 1
        rank = 1
        count = 0
        for i in range(M):
            if by2(sort2[i]) == lastvalue:
                count += 1
                results[sort2[i][0]].append(rank)
            else:
                lastvalue = by2(sort2[i])
                rank += count
                results[sort2[i][0]].append(rank)
                count = 1

        lastvalue = 1
        rank = 1
        count = 0
        for i in range(M):
            if by3(sort3[i]) == lastvalue:
                count += 1
                results[sort3[i][0]].append(rank)
            else:
                lastvalue = by3(sort3[i])
                rank += count
                results[sort3[i][0]].append(rank)
                count = 1

        lastvalue = 1
        rank = 1
        count = 0
        for i in range(M):
            if by4(sort4[i]) == lastvalue:
                count += 1
                results[sort4[i][0]].append(rank)
            else:
                lastvalue = by4(sort4[i])
                rank += count
                results[sort4[i][0]].append(rank)
                count = 1

        for n in results:
            rank = min(n)
            for i in range(4):
                if rank == n[i]:
                    print(str(rank) + ":" + str(i + 1))
                    break
        print()

    except:
        break

#include<vector>
(721)#include<limits.h>
#include<iostream>
(720)#include<algorithm>
using namespace std;


struct AwardInfo {
    int index, gold, medals, population;
    double gold_ratio, medal_ratio;
};


bool cmp1(AwardInfo &a, AwardInfo &b) {
    return a.gold>=b.gold;
}
bool cmp2(AwardInfo &a, AwardInfo &b) {
    return a.medals>=b.medals;
}
bool cmp3(AwardInfo &a, AwardInfo &b) {
    return a.gold_ratio>=b.gold_ratio;
}
bool cmp4(AwardInfo &a, AwardInfo &b) {
    return a.medal_ratio>=b.medal_ratio;
}


int main() {
    int n, m;
    while(cin>>n>>m) {
        vector<AwardInfo> dic1(n);
        for(int i=0; i<n; ++i) {
            AwardInfo a;
            a.index=i;
            cin>>a.gold>>a.medals>>a.population;
            if(a.population == 0) {
                if(a.gold == 0) a.gold_ratio=0;
                else a.gold_ratio=INT_MAX;
                if(a.medals == 0) a.medal_ratio=0;
                else a.medal_ratio=INT_MAX;
            } else {
                a.gold_ratio = double(a.gold)/double(a.population);
                a.medal_ratio = double(a.medals)/double(a.population);
            }
            dic1[i]=a;
        }
        vector<AwardInfo> dic2(dic1.begin(), dic1.end());
        vector<AwardInfo> dic3(dic1.begin(), dic1.end());
        vector<AwardInfo> dic4(dic1.begin(), dic1.end());
        sort(dic1.begin(), dic1.end(), cmp1);
        sort(dic2.begin(), dic2.end(), cmp2);
        sort(dic3.begin(), dic3.end(), cmp3);
        sort(dic4.begin(), dic4.end(), cmp4);
        vector<vector<AwardInfo>> d;
        d.emplace_back(dic1);
        d.emplace_back(dic2);
        d.emplace_back(dic3);
        d.emplace_back(dic4);
        int rank_method, min_rank, country_index;
        for(int index=0; index<m; ++index) {
            cin>>country_index;
            min_rank=INT_MAX;
            for(int i=0; i<4; ++i) {
                for(int j=0; j<n; ++j) {
                    if(d[i][j].index==country_index) {
                        int t=j-1;
                        for(; t>=0; --t) {
                            if(i==0) {
                                if(!cmp1(d[i][j], d[i][t])) break;
                            } else if(i==1) {
                                if(!cmp2(d[i][j], d[i][t])) break;
                            } else if(i==2) {
                                if(!cmp3(d[i][j], d[i][t])) break;
                            } else if(i==3) {
                                if(!cmp4(d[i][j], d[i][t])) break;
                            }
                        }
                        j=t+1;
                        if(j<min_rank) {
                            min_rank=j;
                            rank_method=i+1;
                        }
                        break;
                    }
                }
            }
            cout<<min_rank+1<<':'<<rank_method<<endl;
        }
        cout<<endl;
    }
}

//
//  main.cpp
//  奥运排名
//

#include<iostream>
(720)#include<algorithm>
#include<cstdio>
using namespace std;
typedef struct country{
    int ID;
    int seq;//最终排列的名次
    int sortWay;//最优排序的方式
    int Seq[4];//1-4不同的排序方式 当前城市的名次
    double goldNum;//金牌数
    double comNum;//奖牌数
    double personNum;//人数
    double goldRatio;//金牌比例
    double comRatio;//奖牌比例
}country;
const int MAXN=205;//最多不超过200个国家
const int Max=65535;
bool cmp(country a,country b)
{
    if(a.ID<b.ID)
        return true;
    return false;
}
bool cmp1(country a,country b)
{
    if(a.goldNum>b.goldNum)
        return true;
    return false;//金牌数越多排名越靠前
}
bool cmp2(country a,country b)
{
    if(a.comNum>b.comNum)
        return true;
    return false;
}
bool cmp3(country a,country b)
{
    if(a.goldRatio>b.goldRatio)
        return true;
    return false;
}
bool cmp4(country a,country b)
{
    if(a.comRatio>b.comRatio)
        return true;
    return false;
}


void sortCountry(country a[],int num)//num代表数组的数量
{
   
    sort(a,a+num,cmp1); //按金牌数排名
    for(int i=0;i<num;i++)
        a[i].Seq[0]=i+1;
    for(int i=1;i<num;i++)
        if(a[i].goldNum==a[i-1].goldNum)
            a[i].Seq[0]=a[i-1].Seq[0];//考虑并列排名
    
    sort(a,a+num,cmp2); //按奖牌数排名
    for(int i=0;i<num;i++)
        a[i].Seq[1]=i+1;
    for(int i=1;i<num;i++)
        if(a[i].comNum==a[i-1].comNum)
            a[i].Seq[1]=a[i-1].Seq[1];//考虑并列排名
    
    sort(a,a+num,cmp3); //按金牌人口比排名
    for(int i=0;i<num;i++)
        a[i].Seq[2]=i+1;
    for(int i=1;i<num;i++)
        if(a[i].goldRatio==a[i-1].goldRatio)
            a[i].Seq[2]=a[i-1].Seq[2];//考虑并列排名
    
    sort(a,a+num,cmp4); //按奖牌人口比排名
    for(int i=0;i<num;i++)
        a[i].Seq[3]=i+1;
    for(int i=1;i<num;i++)
        if(a[i].comRatio==a[i-1].comRatio)
            a[i].Seq[3]=a[i-1].Seq[3];//考虑并列排名
    
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<num;j++)
        {
            if(a[j].seq>a[j].Seq[i])
            {
                a[j].seq=a[j].Seq[i];
                a[j].sortWay=i+1;
            }
        }
    }
    sort(a,a+num,cmp);
    for(int i=0;i<num;i++)
        cout<<a[i].seq<<":"<<a[i].sortWay<<endl;
    
}

int main()
{
    int n,m;//n指输入的国家数，m指参与排名的国家数（顺位排列）
    while(cin>>n>>m)
    {
        country a[MAXN];
        for(int i=0;i<n;i++)
        {
            cin>>a[i].goldNum>>a[i].comNum>>a[i].personNum;//输入金牌数，奖牌数，人口数
            a[i].ID=i;
            a[i].goldRatio=0;a[i].comRatio=0;//先将平均奖牌数和平均金牌数设置为0
            a[i].goldRatio=a[i].goldNum/a[i].personNum;
            a[i].comRatio=a[i].comNum/a[i].personNum;//一般人口不为0，奖牌数可以为0
            a[i].seq=Max;//一开始先将排名设置为最大
            a[i].sortWay=0;//一开始的排名方式是0
        }
        country temp[MAXN];//用来存放需要排名的国家
        int Id;
        for(int i=0;i<m;i++)
        {
            cin>>Id;
            temp[i]=a[Id];
        }
        sortCountry(temp, m);
        cout<<endl;
    }
    
}

 /*用vector<vector<double>>来存放country的信息，这样构成一个二维数组，
  为了之后用sort，所以这里不那么寻常地用一列来存放国家信息，一行是某一个指标，比如金牌数，
  所以总共有4行n列。
  只用一个cmp即可。
*/
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

bool cmp(double a, double b)
{
    return a > b;
}

int main()
{
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        vector<vector<double>> country(4, vector<double>(n));
        for (int i = 0; i<n; i++)
        {
            int gold, medal, plt;        //金牌，奖牌，人口
            double pergold, permedal;    //人均金牌，人均奖牌
            scanf("%d%d%d", &gold, &medal, &plt);
            pergold = (double)gold / plt;   
            if (gold == 0 && plt == 0)      //这里解释一下，因为测试用例***，会有人口零，奖牌零的情况出现
                pergold = 0;            //而如果除数被除数都是0，那么结果是NAN——Not A Number
            permedal = (double)medal / plt;      //而经过调试发现，调用sort的时候，sort会把vector以NAN为分界
            if (medal == 0 && plt == 0)      //分开来，然后各自进行排序，然后就出错了
                permedal = 0;           //你没有人口是拿鬼去参加奥运的么ヽ(｀Д´)ﾉ︵ ┻━┻ ┻━┻ 
            country[0][i] = gold;          //相应的测试用例放在最下面了
            country[1][i] = medal;
            country[2][i] = pergold;
            country[3][i] = permedal;
        }
//////////////因为我们之后对country进行排序，所以要先把要查询的国家的信息存放在另一个vector里///////
        vector<vector<double>> ctrytocmp(4, vector<double>(m));    //country to compare
        for (int i = 0; i<m; i++)
        {
            int idx;
            scanf("%d", &idx);
            ctrytocmp[0][i] = country[0][idx];
            ctrytocmp[1][i] = country[1][idx];
            ctrytocmp[2][i] = country[2][idx];
            ctrytocmp[3][i] = country[3][idx];
        }
//////////////开始sort，这里用了iterator，it是一个存放vector<double>的迭代器，for循环执行四次，iterator每次++后会到下一行
//////////////这种写法也算是二维数组sort的一种方式，所以一开始vector那样设置就而是为了这个，
//****************所以这里感觉就是整个代码的关键了，加星号**************************//
        for (vector<vector<double>>::iterator it = country.begin(); it != country.end(); it++)
        {
            sort(it->begin(), it->end(), cmp);
        }//这里的复杂度应该为O(nlogn) * 4，并且已经对所有信息进行了排序，总体上是O(nlogn)
        //看似有3个循环，实际上其中一个for的数量级是常数
        for (int i = 0; i<m; i++)
        {
            int best = n, method = 1;    //best表示最高排名，method表示方法对应的数字
            for (int j = 0; j<4; j++)
            {
                for (int k = 0; k<n; k++)
                {
                    if (country[j][k] == ctrytocmp[j][i] && best > k + 1)
                    {
                        best = k + 1;
                        method = j + 1;
                        break;
                    }//从前向后遍历，只要碰到和要查询的国家相应的指标相同的项就停止查询，这样就能做到并列排名
                }
                if (best == 1)    //如果已经第一了，就可以break了
                    break;
            }
            printf("%d:%d\n", best, method);
        }    //针对m个要进行查询的国家，遍历，其中还要还要么遍历4*n次，而且输出也在第一层for中进行了
        printf("\n");
    }//while

}//main

/*                        
测试用例:            对应输出应该为:
10 10                1:2
0 9 6                3:4
3 8 5                1:1
6 1 1                1:2
5 9 8                2:3
4 8 1                1:4
0 3 0                3:3
4 4 4                4:1
4 7 6                7:1
3 1 7                1:2
5 9 6
0 1 2 3 4 5 6 7 8 9
*/

我感觉利用面向对象的想法非常清晰

package com.speical.first;

import java.util.Scanner;

/** 
* 奥运会排序问题
* 
* 思路：用类来保存排名和排名方式
* 每次排序完，都对排序后都对国家的排名和排名方式更新
* 1.若当前排名比国家之前的排名小
* 2.若当前排名比国家之前的排名一样，但排序方式比上一次小
* 这两种情况发生时即可更新排名和排名方式
* 
* 我这里的排序算法是选择排序
* @author special
* @date 2018年1月5日 上午10:47:03
*/
public class Pro115 {

    static class Country{
        int goldNum;
        int medalNum;
        int people;
        double goldRate;
        double medalRate;
        int rank;
        int style;

        public Country(int goldNum, int medalNum, int people){
            this.goldNum = goldNum;
            this.medalNum = medalNum;
            this.people = people;
            goldRate = goldNum / (people * 1.0);
            medalRate = medalNum / (people * 1.0);
            rank = Integer.MAX_VALUE;
            style = Integer.MAX_VALUE;
        }    
    }

    public static boolean more(Country c1, Country c2, int flag){
        switch (flag) {
        case 1: return c1.goldNum > c2.goldNum;
        case 2: return c1.medalNum > c2.medalNum;
        case 3: return c1.goldRate > c2.goldRate;
        case 4: return c1.medalRate > c2.medalRate;
        }
        return false;
    }

    public static void selectSort(Country[] staySort, int flag){
        int length = staySort.length;
        int max;
        Country[] temp = staySort.clone(); //克隆一下待排数组
        for(int i = 0; i < length - 1; i++){
            max = i;
            for(int j = i + 1; j < length; j++){
                if(more(temp[j], temp[max], flag)){
                    max = j;
                }
            }
            if(max != i){
                Country item = temp[i];
                temp[i] = temp[max];
                temp[max] = item;
            }
        }
        int rank = 1;
        if(temp[0].rank > rank || (temp[0].rank == rank && temp[0].style > flag)){
            temp[0].rank = rank;
            temp[0].style = flag;
        }
        for(int i = 1; i < length; i++){
            if(more(temp[i - 1], temp[i], flag)){
                rank = i + 1;
            }
            if(temp[i].rank > rank || (temp[i].rank == rank && temp[i].style > flag)){
                temp[i].rank = rank;
                temp[i].style = flag;
            }
        }

    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int m = input.nextInt();
            Country[] countries = new Country[n];
            for(int i = 0; i < n; i++){
                countries[i] = new Country(input.nextInt(), input.nextInt(), input.nextInt());
            }
            Country[] staySort = new Country[m];
            for(int i = 0; i < m; i++){
                staySort[i] = countries[input.nextInt()];
            }
            selectSort(staySort, 1);
            selectSort(staySort, 2);
            selectSort(staySort, 3);
            selectSort(staySort, 4);
            for(int i = 0; i < m; i++){
                System.out.println(staySort[i].rank + ":" + staySort[i].style);
            }
            System.out.println();
        }
    }

}

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<map>
/*奥运排序问题*/
struct country
{
    double property[5];//人口数、金牌数、奖牌数、金牌人口比例、奖牌人口比例
    int order;//唯一标识一个国家
    multimap<int,int> mark;//不同排序方法的排序结果
    bool operator==(const int &c)
    {
        return order == c;
    }
};
//四种比较函数
bool comp_gold(country con1, country con2)
{
    return con1.property[1]> con2.property[1];
}
bool comp_medal(country con1, country con2)
{
    return con1.property[2] > con2.property[2];
}
bool comp_ratio_g(country con1, country con2)
{
    return con1.property[3] > con2.property[3];
}
bool comp_ratio(country con1, country con2)
{
    return con1.property[4] > con2.property[4];
}
 
int main()
{
    int N, M;
    vector<country> con;
    vector<int> num;
    //函数指针，指向不同函数名进行调用，便于后面用循环进行四种比较
    typedef bool (*funcName)(country, country);
    map<int, funcName> m;
    m[1] = comp_gold;
    m[2] = comp_medal;
    m[3] = comp_ratio_g;
    m[4] = comp_ratio;
 
    while (cin>>N>> M)
    {
        for(int i = 0; i < N; i++)//输入国家数据
        {
            country temp;//临时对象
            cin>>temp.property[1]>>temp.property[2]>>temp.property[0];
            temp.property[3]=temp.property[1]/temp.property[0];
            temp.property[4]=temp.property[2]/temp.property[0];
            temp.order = i;
            con.push_back(temp);
        }
        while (M--)//输入待排序国家序号
        {
            int index;
            cin >> index;
            num.push_back(index);
        }
        //容器迭代器
        vector<int>::iterator it;
        vector<country>::iterator itx;
        //四种排序
        for(int k=1;k<=4;k++)
        {
            sort(con.begin(), con.end(),*m[k]);
            for ( it = num.begin(); it != num.end(); it++)
            {
                int pos = find(con.begin(), con.end(), *it) - con.begin();
                for ( itx = con.begin(); itx != con.end(); itx++)
                {
                    if ((*itx).property[k] == con[pos].property[k])
                    {
                        con[pos].mark.insert(make_pair(itx - con.begin() ,k));
                        break;
                    }
                }
            }
        }
        //输出结果
        for (it = num.begin(); it != num.end(); it++)
        {
            for (itx = con.begin(); itx != con.end(); itx++)
            {
                if ((*itx).order == (*it))
                {
                    cout << (((*itx).mark.begin())->first)+1<<":"
                        << ((*itx).mark.begin())->second<<endl;
                    break;
                }
            }
                 
        }
        cout << endl;
        num.clear();
        con.clear();
    }
    return 0;
}

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
struct node{
    int glod,card,cnt,num;
    double glodRate,cardRate;
    int grade[4];
    node(){}
    node(int glod,int card,int cnt,int num)
        :glod(glod),card(card),cnt(cnt),num(num),
        glodRate((double)glod/cnt),cardRate((double)card/cnt){}
    int getBest(){
        int i,Min=999999999,index;
        for(i=0;i<4;i++)
            if(Min>grade[i]) Min=grade[i],index=i;
        return index;
    }
};
bool cmp1(const node &x,const node &y){
    return x.glod>y.glod;
}
bool cmp2(const node &x,const node &y){
    return x.card>y.card;
}
bool cmp3(const node &x,const node &y){
    return x.glodRate>y.glodRate;
}
bool cmp4(const node &x,const node &y){
    return x.cardRate>y.cardRate;
}
void getGrade(vector<node> &x,int n){
    x[0].grade[n]=1;
    for(int i=1;i<x.size();i++)
        switch(n){
            case 0:
                if(x[i].glod==x[i-1].glod)
                    x[i].grade[n]=x[i-1].grade[n];
                else x[i].grade[n]=i+1;break;
            case 1:
                if(x[i].card==x[i-1].card)
                    x[i].grade[n]=x[i-1].grade[n];
                else x[i].grade[n]=i+1;break;
            case 2:
                if(x[i].glodRate==x[i-1].glodRate)
                    x[i].grade[n]=x[i-1].grade[n];
                else x[i].grade[n]=i+1;break;
            case 3:
                if(x[i].cardRate==x[i-1].cardRate)
                    x[i].grade[n]=x[i-1].grade[n];
                else x[i].grade[n]=i+1;
        }
}
int main(){
    int n,m,i,glod,card,cnt;
    for(;scanf("%d%d",&n,&m)!=EOF&&n&&m;printf("\n")){
        map<int,node> book;
        vector<node> d;
        vector<int> need;
        for(i=0;i<n;i++)
            scanf("%d%d%d",&glod,&card,&cnt),
            book[i]=node(glod,card,cnt,i);
        for(i=0;i<m;i++)
            scanf("%d",&cnt),d.push_back(book[cnt]),need.push_back(cnt);
        sort(d.begin(),d.end(),cmp1),getGrade(d,0);
        sort(d.begin(),d.end(),cmp2),getGrade(d,1);
        sort(d.begin(),d.end(),cmp3),getGrade(d,2);
        sort(d.begin(),d.end(),cmp4),getGrade(d,3);
        for(i=0;i<m;i++) book[d[i].num]=d[i];
        for(i=0;i<need.size();i++)
            printf("%d:%d\n",book[need[i]].grade[book[need[i]].getBest()],
            book[need[i]].getBest()+1);
    }
}