首页 > 试题广场 >

奥运排序问题

[编程题]奥运排序问题
  • 热度指数:14354 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
按要求,给国家进行排名。

输入描述:
有多组数据。
第一行给出国家数N,要求排名的国家数M,国家号从0到N-1。
第二行开始的N行给定国家或地区的奥运金牌数,奖牌数,人口数(百万)。
接下来一行给出M个国家号。


输出描述:
排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例 
对每个国家给出最佳排名排名方式 和 最终排名
格式为: 排名:排名方式
如果有相同的最终排名,则输出排名方式最小的那种排名,对于排名方式,金牌总数 < 奖牌总数 < 金牌人口比例 < 奖牌人口比例 
如果有并列排名的情况,即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4.
每组数据后加一个空行。
示例1

输入

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

输出

1:3
1:1
2:1
1:2

1:1
1:1


#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;
}

注释应该写清楚了慢慢看
编辑于 2020-04-20 09:25:42 回复(0)
是真滴难搞哦!
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct TypeRank
{
    int rank[4];
}TypeRank;
int main()
{
    int N,M;
    while(cin >> N >> M)
    {
        int golds[N],medals[N],populations[N];
        for(int i = 0;i < N;i++)
        {
            cin >> golds[i] >> medals[i] >> populations[i];
        }
        TypeRank trank[M];
        int map[M];
        for(int i = 0;i < M;i++)
        {
            cin >> map[i];
            trank[i].rank[0] = 1;
            trank[i].rank[1] = 1;
            trank[i].rank[2] = 1;
            trank[i].rank[3] = 1;
        }
        for(int i = 0;i < M;i++)
        {
            for(int j = 0;j < M;j++)
            {
                if(j != i)
                {
                    double tg1,tg2,tm1,tm2;
                    if(!golds[map[i]] && !populations[map[i]])
                    {
                        tg1 = 0;
                    }
                    else
                    {
                        tg1 = 1.0 * golds[map[i]] / populations[map[i]];
                    }
                    if(!golds[map[j]] && !populations[map[j]])
                    {
                        tg2 = 0;
                    }
                    else
                    {
                        tg2 = 1.0 * golds[map[j]] / populations[map[j]];
                    }
                    if(!medals[map[i]] && !populations[map[i]])
                    {
                        tm1 = 0;
                    }
                    else
                    {
                        tm1 = 1.0 * medals[map[i]] / populations[map[i]];
                    }
                    if(!medals[map[j]] && !populations[map[j]])
                    {
                        tm2 = 0;
                    }
                    else
                    {
                        tm2 = 1.0 * medals[map[j]] / populations[map[j]];
                    }
                    if(golds[map[i]] < golds[map[j]]) trank[i].rank[0]++;
                    if(medals[map[i]] < medals[map[j]]) trank[i].rank[1]++;
                    if(tg1 < tg2) trank[i].rank[2]++;
                    if(tm1 < tm2) trank[i].rank[3]++;
                }
            }
        }
        for(int i = 0;i < M;i++)
        {
            int min = trank[i].rank[0],index = 0;
            for(int j = 0;j < 4;j++)
            {
                if(trank[i].rank[j] < min)
                {
                    min = trank[i].rank[j];
                    index = j;
                }
            }
            cout << min << ":" << index + 1 << endl;
        }
        cout << endl;
    }
}
发表于 2021-01-15 21:18:41 回复(0)
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





编辑于 2020-07-07 22:11:47 回复(0)
这道题用C++真的是有点麻烦...
#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;
    }
}

发表于 2020-05-08 21:35:39 回复(0)
这个坑好多啊。
我是直接创建个结构体,记录国家号、金牌数、奖牌数、金牌比例、奖牌比例以及 四个排名和 最终排名、最终方法。
四个排名分别在四次排序 先后赋值。最终使用循环检查结构体,给最终排名赋值。
遇到的坑:
1.并列第几并不影响后面不并列的名次
2.人口数可能为0,这样金牌/奖牌比例可能为 0 或 无穷大
3.金牌为0,人口为0的时候 金牌比例是0而不是无穷大
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXGOAL 99999
using namespace std;

struct country{
    int id;//国家号
    int gold;//金牌总数
    int medal;//奖牌总数
    int people;//人口数
    double ratioG;//金牌人口比例
    double ratioM;//奖牌人口比例
    int rankG=-1;//按金牌排名的位置
    int rankM=-1;//按奖牌
    int rankGR=-1;//按金牌人口比例
    int rankMR=-1;//按奖牌人口比例
    int finalRank=-1;
    int finalNum=-1;
};
bool cmp0(country c1, country c2){
    return c1.id<c2.id;
}
bool cmp1(country c1, country c2){
    return c1.gold>c2.gold;
}
bool cmp2(country c1, country c2){
    return c1.medal>c2.medal;
}
bool cmp3(country c1, country c2){
    return c1.ratioG>c2.ratioG;
}
bool cmp4(country c1, country c2){
    return c1.ratioM>c2.ratioM;
}

country con[10];//输入的数据
int testId[10];//用于排名的id
country testCon[10];//用于排名的国家

int main(){
    int N,M;
    while(cin>>N){
        cin>>M;
        for(int i=0;i<N;i++){
            cin>>con[i].gold>>con[i].medal>>con[i].people;//输入金牌、奖牌、人口
            con[i].id=i;//国家号
            if(con[i].people==0){//人口数可能为0,这里注意,为0后 同为无穷大默认相等
                //金牌数和奖牌数也可能为0 啊啊啊啊啊啊
                if(con[i].gold==0)
                    con[i].ratioG=0;
                else
                    con[i].ratioG=MAXGOAL;
                if(con[i].medal==0)
                    con[i].ratioM=0;
                else
                    con[i].ratioM=MAXGOAL;
            }
            else{
                con[i].ratioG=(con[i].gold*1.0)/(con[i].people*1.0);
                con[i].ratioM=(con[i].medal*1.0)/(con[i].people*1.0);
            }
        }
        for(int i=0;i<M;i++)
            cin>>testId[i];//输入需要排序的国家号
        for(int i=0;i<M;i++)
            testCon[i]=con[testId[i]];//放到另一个数组里
        //现在是要对testCon里的进行排序
        sort(testCon,testCon+M,cmp1);//按金牌总数排名,赋值rankG
        for(int i=0;i<M;i++){
            if(i==0)
                testCon[i].rankG=1;
            else{
                if(testCon[i].gold==testCon[i-1].gold)
                    testCon[i].rankG=testCon[i-1].rankG;
                else testCon[i].rankG=i+1;//注意,例子,如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4.而不是1,2,2,3
            }
        }
        sort(testCon,testCon+M,cmp2);//按奖牌总数排名,赋值rankM
        for(int i=0;i<M;i++){
            if(i==0)
                testCon[i].rankM=1;
            else{
                if(testCon[i].medal==testCon[i-1].medal)
                    testCon[i].rankM=testCon[i-1].rankM;
                else testCon[i].rankM=i+1;
            }
        }
        sort(testCon,testCon+M,cmp3);//按金牌人口比例排名,赋值rankGR
        for(int i=0;i<M;i++){
            if(i==0)
                testCon[i].rankGR=1;
            else{
                if(testCon[i].ratioG==testCon[i-1].ratioG)
                    testCon[i].rankGR=testCon[i-1].rankGR;
                else testCon[i].rankGR=i+1;
            }
        }
        sort(testCon,testCon+M,cmp4);//按奖牌人口比例排名,并为finalRank赋值默认为rankMR,finkalNum默认为4
        for(int i=0;i<M;i++){
            if(i==0)
                testCon[i].rankMR=1;
            else{
                if(testCon[i].ratioM==testCon[i-1].ratioM)
                    testCon[i].rankMR=testCon[i-1].rankMR;
                else testCon[i].rankMR=i+1;
            }
            testCon[i].finalRank=testCon[i].rankMR;
            testCon[i].finalNum=4;
        }
        sort(testCon,testCon+M,cmp0);//按id排序并输出
        for(int i=0;i<M;i++){
            if(testCon[i].finalRank>=testCon[i].rankGR){
                testCon[i].finalRank=testCon[i].rankGR;
                testCon[i].finalNum=3;
            }
            if(testCon[i].finalRank>=testCon[i].rankM){
                testCon[i].finalRank=testCon[i].rankM;
                testCon[i].finalNum=2;
            }
            if(testCon[i].finalRank>=testCon[i].rankG){
                testCon[i].finalRank=testCon[i].rankG;
                testCon[i].finalNum=1;
            }
        }
        for(int i=0;i<M;i++){
            cout<<testCon[i].finalRank<<":"<<testCon[i].finalNum<<endl;
        }
        
        //信息输出
//        for(int i=0;i<M;i++){
//            cout<<testCon[i].id<<" "<<testCon[i].gold<<" "<<testCon[i].medal<<" "<<testCon[i].people<<" "<<testCon[i].ratioG<<" "<<testCon[i].ratioM<<" "<<testCon[i].rankG<<" "<<testCon[i].rankM<<" "<<testCon[i].rankGR<<" "<<testCon[i].rankMR<<" "<<endl;
//        }
        
        
        cout<<endl;
    }
}


编辑于 2020-01-27 21:37:15 回复(3)
不需要排序,所以也就没必要用结构体了
注意有些国家的金牌或奖牌和人口同时为0
#include <stdio.h>
#define N 10
int main() {
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        int temp[N][3];
        for(int i=0; i<n; i++) {
            scanf("%d%d%d",&temp[i][0],&temp[i][1],&temp[i][2]);
        }
        float data[N][4];
        int rank[N][4]= {0};
        for(int i=0; i<m; i++) {
            int country_id;
            scanf("%d",&country_id);
            data[i][0]=temp[country_id][0];
            data[i][1]=temp[country_id][1];
            data[i][2]=temp[country_id][0]?data[i][0]/temp[country_id][2]:0;
            data[i][3]=temp[country_id][1]?data[i][1]/temp[country_id][2]:0;
        }
        for(int i=0; i<m; i++) {
            for(int j=0; j<m; j++) {
                for(int k=0; k<4; k++) {
                    if(data[j][k]>data[i][k]) {
                        rank[i][k]++;
                    }
                }
            }
        }
        for(int i=0; i<m; i++) {
            int min=0;
            for(int j=1; j<4; j++) {
                if(rank[i][j]<rank[i][min]) {
                    min=j;
                }
            }
            printf("%d:%d\n",rank[i][min]+1,min+1);
        }
        printf("\n");
    }
}



编辑于 2020-04-17 01:11:58 回复(7)
//虽然花了好几个小时.....代码写得很糙,还是想分享一下啊,顺便回顾一下解题思路
解题过程大体如下: 


1.按照题意确定结构体 (大体根据输入的数据以及要输出的数据来确定结构题的成员)
    参考:
struct Record{
    int id;//每个国家都有一个唯一的id,从0开始
    int pop;//人口
    double ans[4];//ans[0]、ans[1]、ans[2]、ans[3],分别表示金牌数、奖牌数、金牌人口比、奖牌人口比
  
    int rank[5];//记录各种方式下的排名,rank[4]用来保存最佳的排名
   
    int sort;    //记录最佳排名的方式     按照题意方式有四种(编号为1,2,3,4)
};
2.设计比较函数cmp
   因为题目要求按照四种标准来排序,且均是按照同样的大小顺序来排序,故可进行画简处理(否则得设计四个功能相似的比较函数)
参考:
    int now; //正好与ans数据对应起来,now从0,1,2,3依次比较ans[0],ans[1]....,
bool cmp(Record a,Record b)
{
    return a.ans[now]>b.ans[now];
   
}

3.计算rank数组以及sort,为了保证数据的一致,将需要参与排序(也即需要被修改的部分)重新放置到新的数组country[]中,所有计算工作完成以后,再将其复制给原数组re[]

    Record country[M];    
    int ids[M];//参与排名的国家
    for(int i=0;i<M;i++)
    {    
        
        scanf("%d",&ids[i]);//输入参与排名的国家id
        country[i]=re[ids[i]];
        
        country[i].rank[4]=100000;
        
    }
 


    for(now=0;now<4;now++) //分别按照四种排序方式依次计算rank[now]
    {
        sort(country,country+M,cmp);//排序
   
       
        country[0].rank[now]=1;
        if(country[0].rank[now]<country[0].rank[4])
        {
            country[0].rank[4]=1;
            country[0].sort=now+1;
        }
        for(int i=1;i<M;i++)//定级
        {
            if(country[i].ans[now]==country[i-1].ans[now])//总数相同
                country[i].rank[now]=country[i-1].rank[now];
            else
                country[i].rank[now]=i+1;

            if(country[i].rank[now]<country[i].rank[4])
            {
                country[i].rank[4]=country[i].rank[now];
                country[i].sort=now+1;
            }
        }
    
       
    }

4.输出:
因题意需要按照输入的国家顺序依次输出排序结果,故用ids数组来保存初始输入的国家id顺序。
在输入时用re数组来保存所有国家的信息,为了方便输出,初始化时将re数组的下标与国家的id号对等起来
    Record re[N];
    for(int i=0;i<N;i++) //输入国家信息
    {
        re[i].id=i;//数组下标即是国家id
        scanf("%lf %lf %d",&re[i].ans[0],&re[i].ans[1],&re[i].pop);
        re[i].ans[2]=(double)re[i].ans[0]/re[i].pop;
        re[i].ans[3]=(double)re[i].ans[1]/re[i].pop;

    }
   
完整代码:
    

#include<stdio.h>
#include<algorithm>
using namespace std;
   

struct Record{
    int id;//0....
    int pop;
    double ans[4];//double gold 0; medal 1;double gp 2,mp 3;
    //奖牌数
    //人口数
    int rank[5];//记录各种方式下的排名
   
    int sort;   
};

int now;
bool cmp(Record a,Record b)
{
    return a.ans[now]>b.ans[now];
   
}



   

int main()
{

   
    int N,M;
   
while(    scanf("%d %d",&N,&M)!=EOF){
    Record re[N];
    for(int i=0;i<N;i++)
    {
        re[i].id=i;//数组下标即是国家id
        scanf("%lf %lf %d",&re[i].ans[0],&re[i].ans[1],&re[i].pop);
        re[i].ans[2]=(double)re[i].ans[0]/re[i].pop;
        re[i].ans[3]=(double)re[i].ans[1]/re[i].pop;

    }
   
    Record country[M];     
    int ids[M];//参与排名的国家
    for(int i=0;i<M;i++)
    {   
       
        scanf("%d",&ids[i]);//输入参与排名的国家id
        country[i]=re[ids[i]];
       
        country[i].rank[4]=100000;
       
    }


    for(now=0;now<4;now++)
    {
        sort(country,country+M,cmp);//排序
   
       
        country[0].rank[now]=1;
        if(country[0].rank[now]<country[0].rank[4])
        {
            country[0].rank[4]=1;
            country[0].sort=now+1;
        }
        for(int i=1;i<M;i++)//定级
        {
            if(country[i].ans[now]==country[i-1].ans[now])//总数相同
                country[i].rank[now]=country[i-1].rank[now];
            else
                country[i].rank[now]=i+1;

            if(country[i].rank[now]<country[i].rank[4])
            {
                country[i].rank[4]=country[i].rank[now];
                country[i].sort=now+1;
            }
        }
    
       
    }


   
    for(int i=0;i<M;i++) //将修改改回原始数组,方便按照输入顺序输出
    {
        re[country[i].id]=country[i];    
    }

    for(int i=0;i<M;i++)
    {
        printf("%d:%d\n",re[ids[i]].rank[4],re[ids[i]].sort);
    }
   
   

    printf("\n");
}
return 0;
}


发表于 2017-01-17 23:37:39 回复(2)
#include <stdio.h>
//不用排序,只要遇见比自己记录高的把排名+1就行

//国家结构体
struct Kuni {
    float gold;
    float model;
    float civil;
    float goldB;
    float modelB;
};


int main()
{
    int n = 0;
    int m = 0;
    int w[1000];//标记参与排名的国家
    struct Kuni kuni[1000];
    while (scanf("%d %d", &n, &m) == 2)
    {
        //输入存入国家数组
        for (int i = 0; i<n; i++)
        {
            scanf("%f %f %f", &kuni[i].gold, &kuni[i].model, &kuni[i].civil);
            if (kuni[i].civil == 0)kuni[i].civil = 0.000001;
            kuni[i].goldB = kuni[i].gold / kuni[i].civil;
            kuni[i].modelB = kuni[i].model / kuni[i].civil;

        }

        //输入记录要排名的国家
        for (int i = 0; i<m; i++)
        {
            int temp = 0;
            scanf("%d", &temp);
            w[temp] = 1;
        }

        //国家排名
        for (int i = 0; i<n; i++)
        {
            int goldR = 1;
            int modelR = 1;
            int goldBR = 1;
            int modelBR = 1;

            //某些国家不参与排名
            if (w[i] != 1)
                continue;

            //排名统计,只要有比自己大的,自己排名就+1
            for (int j = 0; j<n; j++)
            {
                if (kuni[j].gold > kuni[i].gold)
                    goldR++;
                if (kuni[j].model > kuni[i].model)
                    modelR++;
                if (kuni[j].goldB > kuni[i].goldB)
                    goldBR++;
                if (kuni[j].modelB > kuni[i].modelB)
                    modelBR++;
            }

            //如果人口为0且被除数不为0,则比例都为第一名
            if (kuni[i].civil < 1)
            {
                if (kuni[i].gold != 0)goldBR = 1;
                if (kuni[i].model != 0)modelBR = 1;
            }

            //查找四种排序方法里的最小排名
            if (goldBR <= modelBR)
            {
                if (modelR <= goldBR)
                {
                    if (goldR <= modelR)
                        printf("%d:%d\n", goldR, 1);
                    else
                        printf("%d:%d\n", modelR, 2);
                }
                else
                {
                    if (goldR <= goldBR)
                        printf("%d:%d\n", goldR, 1);
                    else
                        printf("%d:%d\n", goldBR, 3);
                }
            }
            else
            {
                if (modelR <= modelBR)
                {
                    if (goldR <= modelR)
                        printf("%d:%d\n", goldR, 1);
                    else
                        printf("%d:%d\n", modelR, 2);
                }
                else
                {
                    if (goldR <= modelBR)
                        printf("%d:%d\n", goldR, 1);
                    else
                        printf("%d:%d\n", modelBR, 4);
                }
            }
        }
        printf("\n");
    }
    return 0;
}

编辑于 2019-03-13 10:54:07 回复(0)
//
//  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;
    }
    
}
最原始的方法。思路不难///这道题做的太费劲了
发表于 2020-04-19 18:36:36 回复(0)
这个题用面向对象的思想很好,这题比较坑的地方在于。人口可能为0:
编辑于 2019-07-01 23:36:38 回复(8)
这个题用函数指针是妙不可言啊~
发表于 2019-06-28 15:33:26 回复(0)
 /*用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
*/

发表于 2018-02-15 11:43:19 回复(0)

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

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();
        }
    }

}
发表于 2018-01-05 11:56:49 回复(1)
#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);
    }
}

编辑于 2017-10-22 14:10:10 回复(0)
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;
struct Nation{//直接求四种排名的值
    int gold;
    int total;
    double ave_gold;
    double ave_total;
};
bool cmp1(int lhs,int rhs){//逆序排序
    if(lhs>rhs) return true;
    else return false;
}
bool cmp2(double lhs,double rhs){//逆序排序
    if(lhs>rhs) return true;
    else return false;
}
int main(){
    int n,m;
    double people;
    Nation nation[1001];
   
    while(scanf("%d%d",&n,&m)!=EOF){
        vector<int> sort1,sort2;
        vector<double> sort3,sort4;
        //输入操作+vector存储
        for(int i=0;i<n;i++){
            scanf("%d%d%lf",&nation[i].gold,&nation[i].total,&people);
            nation[i].ave_gold=nation[i].gold/people;
            nation[i].ave_total=nation[i].total/people;
            if(nation[i].gold==0&&people==0) nation[i].ave_gold=0;//额外的坑(要注意有0/0的情况)
            sort1.push_back(nation[i].gold);
            sort2.push_back(nation[i].total);
            sort3.push_back(nation[i].ave_gold);
            sort4.push_back(nation[i].ave_total);
        }
        //排序
        sort(sort1.begin(),sort1.end(),cmp1);
        sort(sort2.begin(),sort2.end(),cmp1);
        sort(sort3.begin(),sort3.end(),cmp2);
        sort(sort4.begin(),sort4.end(),cmp2);
        /*
        for(int i=0;i<n;i++) printf("%d ",sort1[i]);
        printf("\n");
        for(int i=0;i<n;i++) printf("%d ",sort2[i]);
        printf("\n");
        for(int i=0;i<n;i++) printf("%lf ",sort3[i]);
        printf("\n");
        for(int i=0;i<n;i++) printf("%lf ",sort4[i]);
        printf("\n");*/
        int seq;
        for(int i=0;i<m;i++){//遍历要输出的国家
            scanf("%d",&seq);
            int way[4];//记录四种排序方式的名次
            int best_rank=300;//最优排名
            int best_way;//最优排名方式
            for(int k=0;k<sort1.size();k++){//第一种排序的名次
                if(sort1[k]==nation[seq].gold) {
                    way[1]=k;
                    break;
                }
            }
            for(int k=0;k<sort2.size();k++){//第二种排序的名次
                if(sort2[k]==nation[seq].total) {
                    way[2]=k;
                    break;
                }
            }
            for(int k=0;k<sort3.size();k++){//第三种排序的名次
                if(sort3[k]==nation[seq].ave_gold) {
                    way[3]=k;
                    break;
                }
            }
            for(int k=0;k<sort4.size();k++){//第四种排序的名次
                if(sort4[k]==nation[seq].ave_total) {
                    way[4]=k;
                    break;
                }
            }
            //求最佳排名
            for(int k=1;k<=4;k++){
                if(way[k]<best_rank){
                    best_rank=way[k];
                    best_way=k;
                }
            }
            printf("%d:%d\n",best_rank+1,best_way);
        }
        printf("\n");

    }
    return 0;
}
编辑于 2024-03-07 15:33:16 回复(0)
这道题,我两个月前第一次的时候,做得很复杂,又是结构体,又是各种compare函数,把所有的排名都排出来的再进行比较,实则没必要
用一个二维数组初始化数据即可,排名则是通过遍历相同列的数组,大的排名加一,最后选择排名方式靠前的,排名小的。
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

double state[100][4];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=-1){
        for(int i=0;i<n;i++){
            double people;
            scanf("%lf%lf%lf",&state[i][0],&state[i][1],&people);
            //下面这些判断是为了通过0/0的情况
            if(state[i][0]==0){
                state[i][2]=0;
            }else{
                state[i][2]=state[i][0]/people;
            }
            if(state[i][1]==0){
                state[i][3]=0;
            }else{
                state[i][3]=state[i][1]/people;
            }
        }

        for(int i=0,sNum;i<m;i++){
            scanf("%d",&sNum);

            int order=n;
            int type=0;
            //四种排序方式,哪种排序方式排名更小,就用哪个
            for(int j=0;j<4;j++){
                //temp记录有多少比我的大的
                int temp=0;
                for(int k=0;k<n;k++){
                    if(state[k][j]>state[sNum][j]){
                        temp+=1;
                    }
                }
                //排名相同的跳过
                if(temp+1<order){
                    order=temp+1;
                    type=j+1;
                }
            }
            printf("%d:%d\n",order,type);
        }
        printf("\n");
    }
    return 0;
}


发表于 2023-03-18 15:05:21 回复(0)
用面向对象的方法做的,重载了一些操作符。
分为三个过程:输入所有国家数据、进行四趟排序并更新最好的记录、输出记录。
#include <iostream>
(720)#include <vector>
#include <algorithm>

using namespace std;

static int tag;
struct Country {
    int no;

    int v1;
    int v2;
    int v3;

    float r1;
    float r2;

    bool operator < (const Country & c)const {
        switch(tag) {
        case 1:
            return v1 > c.v1;
        case 2:
            return v2 > c.v2;
        case 3:
            return r1 > c.r1;
        default:
            return r2 > c.r2;
        }
    }

    friend istream& operator >> (istream& in, Country& c) {
        cin >> c.v1 >> c.v2 >> c.v3;
        c.r1 = (float)c.v1 / (float)c.v3;
        c.r2 = (float)c.v2 / (float)c.v3;

        return in;
    }
};

struct BestRecord {
    int way;
    int v;
    BestRecord() {
        way = -1;
        v = -1;
    }
};

void renew_record(int t, vector<Country>& c, vector<BestRecord>& r) {
    tag = t;
    int rank = 0;
    stable_sort(c.begin(), c.end());
    for(int i = 0; i < c.size(); ++i) {
        if(i == 0)
            rank = 1;
        else {
            switch(tag) {
            case 1:
                if(c[i].v1 < c[i - 1].v1)
                    rank = i+1;
                break;
            case 2:
                if(c[i].v2 < c[i - 1].v2)
                    rank = i+1;
                break;
            case 3:
                if(c[i].r1 < c[i - 1].r1)
                    rank = i+1;
                break;
            default:
                if(c[i].r2 < c[i - 1].r2)
                    rank = i+1;
                break;

            }
        }
        if(r[c[i].no].way == -1) {
            r[c[i].no].way = tag;
            r[c[i].no].v = rank;
        } else {
            if(rank < r[c[i].no].v) {
                r[c[i].no].way = tag;
                r[c[i].no].v = rank;
            }
        }
    }
}

int main() {
    int n, m;
    vector<Country> countrys;
    vector<BestRecord> records;
    while(cin >> n >> m) {
        countrys.clear();
        countrys.resize(n);
        records.clear();
        records.resize(n);
        for(int i = 0; i < n; ++i) {
            cin >> countrys[i];
            countrys[i].no = i;
        }
        renew_record(1, countrys, records);
        renew_record(2, countrys, records);
        renew_record(3, countrys, records);
        renew_record(4, countrys, records);

        for(int i = 0; i < m; ++i) {
            int c;
            cin >> c;
            cout << records[c].v << ":" << records[c].way << endl;
        }
        cout << endl;
    }
    return 0 ;
}


编辑于 2020-03-09 17:52:09 回复(0)
8 / 10的代码
nnd的人口还有为0的
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <climits>
using namespace std;

typedef struct Nation {
    int gold;
    int reward;
    int population;
    double gold_popu;
    double reward_popu;
    int sno;
    int rank;
} Nation;
vector<Nation> nations;

bool cmp1(Nation a, Nation b) {
    return a.gold >= b.gold;
}

bool cmp2(Nation a, Nation b) {
    return a.reward >= b.reward;
}

bool cmp3(Nation a, Nation b) {
    return a.gold_popu >= b.gold_popu;
}

bool cmp4(Nation a, Nation b) {
    return a.reward_popu >= b.reward_popu;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        nations.clear();
        int i = 0;
        int cnt = n;
        while (n--) {
            Nation na;
            cin >> na.gold >> na.reward >> na.population;
            if(na.population == 0){
                na.gold_popu = na.gold * 1.0 / 0.001;
                na.reward_popu = na.reward * 1.0 / 0.001;
            }else{
                na.gold_popu = na.gold ? na.gold * 1.0 / na.population : 0;
                na.reward_popu = na.reward ? na.reward * 1.0 / na.population : 0;
            }
            na.sno = i++;
            nations.push_back(na);
        }
        int cntm = m;
        while (m--) {
            int a;
            cin >> a;
            int minn = cnt + 1;
            int mini = 0;
            for (i = 0; i < 4; i++) {
                if (i == 0) {
                    sort(nations.begin(), nations.end(), cmp1);
                    int pre = 0;
                    nations[pre].rank = 1;
                    for (int j = 1; j < cnt; j++) {
                        if (nations[j].gold == nations[pre].gold) {
                            nations[j].rank = nations[pre].rank;
                        } else {
                            nations[j].rank = j + 1;
                            pre = j;
                        }
                    }
                } else if (i == 1) {
                    sort(nations.begin(), nations.end(), cmp2);
                    int pre = 0;
                    nations[pre].rank = 1;
                    for (int j = 1; j < cnt; j++) {
                        if (nations[j].reward == nations[pre].reward) {
                            nations[j].rank = nations[pre].rank;
                        } else {
                            nations[j].rank = j + 1;
                            pre = j;
                        }
                    }
                } else if (i == 2) {
                    sort(nations.begin(), nations.end(), cmp3);
                    int pre = 0;
                    nations[pre].rank = 1;
                    for (int j = 1; j < cnt; j++) {
                        if (abs(nations[j].gold_popu - nations[pre].gold_popu) <= 1e-6) {
                            nations[j].rank = nations[pre].rank;
                        } else {
                            nations[j].rank = j + 1;
                            pre = j; // 更新pre
                        }
                    }
                } else { // i = 3
                    sort(nations.begin(), nations.end(), cmp4);
                    int pre = 0;
                    nations[pre].rank = 1;
                    for (int j = 1; j < cnt; j++) {
                        if (abs(nations[j].reward_popu - nations[pre].reward_popu) <= 1e-6) { // 并列排名
                            nations[j].rank = nations[pre].rank;
                        } else {
                            nations[j].rank = j + 1;
                            pre = j;
                        }
                    }
                }
                for (int j = 0; j < cnt; j++) { // 寻找最佳排名
                    if (nations[j].sno == a) { // 序号相同
                        if (minn > nations[j].rank) {
                            minn = nations[j].rank;
                            mini = i + 1;
                        }
                    }
                }
            }
            cout << minn << ":" << mini << endl;
        }
        cout << endl;
    }
    return 0;
}


发表于 2024-03-10 10:40:42 回复(0)
这题以为看了题解就会写了,结果除开算法外还是到处踩坑
#include <stdio.h>
#include <iostream>
using namespace std;
#define M 10
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        int all[n][3];
        // 总共给n个国家的信息,列标:0是金牌 1是奖牌 2是人数,输入数据都是整型,用int就可以存,算比例时再用float
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", &all[i][0], &all[i][1], &all[i][2]);
        }
        float part[m][4];
        // 其中只有m个指定id的国家参与排名,列表:0金牌 1奖牌 2金牌占比 3奖牌占比(最后争取表示类型要+1)
        // 因为排名算法一样,干脆存在一起都用float型
        for (int i = 0; i < m; i++) {
            int id;
            scanf("%d", &id);
            part[i][0] = all[id][0];
            part[i][1] = all[id][1];
            /* 两个float作除法运算,4种情况
            1. A/A = A  ————只要不因为结果太小下溢为0,结果就正确
            2. A/0 = inf ————在本题中,就按照inf,即比任何数可表示的具体的数都大
            3. 0/A = 0
            4. 0/0 = NaN ————在本题中,结果按最小值0计,否则结果nan无法与其他任何数比大小
            所以本题A/A和A/0正常做除法,0/A和0/0结果统一为0
             */
            part[i][2] = all[id][0] ? part[i][0] / all[id][2] : 0;  // 用float型/int型,否则没有小数部分
            part[i][3] = all[id][1] ? part[i][1] / all[id][2] : 0;
        }

        int rank[M][4] = {0};  // m个国家4种排名的数组,初始化为0。
        /* 为什么用define的常量M, 而不直接用输入的m?(以下说法来源几个博客文章)
        1. C++不支持变长数组,变长数组指————用变量指定数组元素个数,编译时无法确定大小,运行时才确定大小
        2. 即使编译器优化实现了类似C的变长数组,变长数组本身都是不允许初始化值的,报错为error: variable-sized object may not be initialized
        3. 变长数组 ≠ 动态数组,使用malloc分配内存创建的数组叫做 “动态数组”,分配的空间在堆区
        4. 变长数组是局部变量,在栈区分配空间,变量作用域结束后结汇释放
        5. 使用gdb打印基址寄存器的值、栈顶指针的值、变长数组起始地址,可以验证变长数组的地址在栈区地址范围内
        6. C标准库中的alloca函数,是基于栈的内存分配,用alloca分配空间的数组和变长数组一样不需要手动释放
        7. 用gdb打印int *p = (int*)alloca(size) 和 int arr[size] 的汇编指令,发现二者的底层实现是比较类似的
        8. 变长数组的应用场景为小型机,比如很多嵌入式环境,因为资源有限没有堆内存,但又需要改变数组大小,就可以使用变长数组
        9. 变长数组的使用最好限定大小,否则有栈溢出风险
         */
        // 名次是从1开始的,遇到比自己大的排名++,但是初始化为1需要遍历,所以干脆最后输出时再+1
        // 排名方式序号也是从1开始: 1 金牌总数, 2 奖牌总数, 3 金牌人口比例, 4 奖牌人口比例,所以输出时也要+1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                for (int type = 0; type < 4; type++) {
                    if (part[i][type] < part[j][type]) {
                        rank[i][type]++;
                    }
                }
            }
        }
        // 找出4种排名中排名最好的一种,输出 “排名:排名方式\n”
        for (int i = 0; i < m; i++) {
            int bestRank = rank[i][0], bestType = 0;
            for (int type = 1; type < 4; type++) {
                if (rank[i][type] < bestRank) {
                    bestRank = rank[i][type];
                    bestType = type;
                }
            }
            printf("%d:%d\n", bestRank + 1, bestType + 1);
        }
        printf("\n");
    }
    return 0;
}


发表于 2024-03-06 16:46:56 回复(0)
#include <algorithm>
#include <array>
#include <iostream>
#include <istream>
using namespace std;

enum Method {   //排序方式
    GOLDS = 1,  //金牌总数
    MEDALS,     //奖牌总数
    GOLD_POPULATION_PROPORTION, //金牌人口比例
    MEDAL_POPULATION_PROPORTION //奖牌人口比例
};

class Country { //国家信息类
  public:
    int order;  //国家次序(从0开始)
    int golds, medals, population;  //奥运金牌数、奖牌数、人口数
    double goldsPopulationProportion,   //金牌人口比例
           medalsPopulationProportion;  //奖牌人口比例
    array<int, 5>rank;  //不同排名方式下的排名

    //重载输入流运算符
    friend istream& operator>>(istream& in, Country& c);

    //重载关系运算符"=="(等于)
    bool operator==(const Country& c)const;
};

Method method;  //当前排序方式

//重载输入流运算符
istream& operator>>(istream& in, Country& c) {
    in >> c.golds >> c.medals >> c.population;
    c.goldsPopulationProportion = c.golds * 1.0 / c.population;
    c.medalsPopulationProportion = c.medals * 1.0 / c.population;
    return in;
}

//重载关系运算符"=="(等于)
bool Country::operator==(const Country& c)const {
    switch (method) {
        case GOLDS:
            return golds == c.golds;
        case MEDALS:
            return medals == c.medals;
        case GOLD_POPULATION_PROPORTION:
            return goldsPopulationProportion == c.goldsPopulationProportion;
        case MEDAL_POPULATION_PROPORTION:
            return medalsPopulationProportion == c.medalsPopulationProportion;
    }
}

//比较函数
bool compare(Country c1, Country c2) {
    switch (method) {
        case GOLDS:
            return c1.golds > c2.golds;
        case MEDALS:
            return c1.medals > c2.medals;
        case GOLD_POPULATION_PROPORTION:
            return c1.goldsPopulationProportion > c2.goldsPopulationProportion;
        case MEDAL_POPULATION_PROPORTION:
            return c1.medalsPopulationProportion > c2.medalsPopulationProportion;
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        auto countries = new Country[n]();  //全部国家
        for (int i = 0; i < n; i++) {
            cin >> countries[i];
        }
        auto sorted_countries = new Country[m]();   //待排序的国家
        for (int i = 0; i < m; i++) {
            int order;  //国家序号
            cin >> order;
            sorted_countries[i] = countries[order];
            sorted_countries[i].order = i;
        }
        delete [] countries;
        for (int i = 1; i <= 4; i++) {
            method = static_cast<Method>(i);
            sort(sorted_countries, sorted_countries + m, compare);
            for (int j = 0; j < m; j++) {
                sorted_countries[j].rank[i]
                    = j > 0
                      && sorted_countries[j] == sorted_countries[j - 1] ?
                      sorted_countries[j - 1].rank[i] : j + 1;
            }
        }
        int* best_rank = new int[m]();      //每个国家的最佳排名
        int* best_method = new int[m]();    //每个国家的最佳排名方式
        for (int i = 0; i < m; i++) {
            int order = sorted_countries[i].order;
            best_rank[order] = m + 1;
            for (int j = 1; j <= 4; j++) {
                if (sorted_countries[i].rank[j] < best_rank[order]) {
                    best_rank[order] = sorted_countries[i].rank[j];
                    best_method[order] = j;
                }
            }
        }
        delete [] sorted_countries;
        for (int i = 0; i < m; i++) {
            cout << best_rank[i] << ":" << best_method[i] << endl;
        }
        cout << endl;
    }
    return 0;
}

发表于 2024-02-04 11:07:49 回复(0)