首页 > 试题广场 >

奥运排序问题

[编程题]奥运排序问题
  • 热度指数:14431 时间限制: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


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)