首页 > 试题广场 >

Mice and Rice (25)

[编程题]Mice and Rice (25)

热度指数：3631 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.
First the playing order is randomly decided for N_P programmers. Then every N_G programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every N_G winners are then grouped in the next match until a final winner is determined.
For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.

输入描述:

Each input file contains one test case.  For each case, the first line contains 2 positive integers: N_P and N_G (<= 1000), the number of programmers and the maximum number of mice in a group, respectively.  If there are less than N_G mice at the end of the player's list, then all the mice left will be put into the last group.  The second line contains N_P distinct non-negative numbers W_i (i=0,...N_P-1) where each W_i is the weight of the i-th mouse respectively.  The third line gives the initial playing order which is a permutation of 0,...N_P-1 (assume that the programmers are numbered from 0 to N_P-1).  All the numbers in a line are separated by a space.

输出描述:

For each test case, print the final ranks in a line.  The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.

示例1

输入

11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3

输出

5 5 5 2 5 5 5 3 1 3 5

算法知识视频讲解

Python

初心者托奇

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = [b[int(i)] for i in input().split()]
d = dict(zip(b,range(a[0])))
e = {i:int((a[0] - 1) // a[1] + 2) for i in range(a[0])}

while len(c) - 1:
    c = [max(c[i:i + a[1]]) for i in range(0,len(c),a[1])]
    e.update({d[i]:(len(c) - 1) // a[1] + 2 for i in c})
e[d[c[0]]] = 1

print(' '.join(map(str,list(e.values()))))

题目本身不难，一步到位

第一排的两个数a，b分别表示总人数和每组的最大人数（非最大人数只可能出现在末组），那么经过第一次比赛，(a - 1) // b + 2可以直接得到没有晋级的排名

然后更新a的值为晋级成功的总人数，那么现在(a - 1) // b + 2依然是没有晋级的排名，以此类推，可以获得除了第1名之外的所有正确排名，然后手动给最后晋级的成员赋值排名1

这样的话可以节省不少代码

编辑于 2020-03-05 21:40:28 回复(0)

Python

人生天地间，忽如远行客

import math
import sys

for s in sys.stdin:
    n,k=[int(x) for x in s.split()]
    r=[[int(t),i,-1]for i,t in enumerate(input().split())]
    p=[int(x) for x in input().split()]
    while True:
        t=0
        p1=[[] for i in range(math.ceil(len(p)/k))]
        p2=p
        for i in range(len(p)):
            if i//k==t:
                p1[t].append(p[i])
            if i%k==k-1:
                t+=1
        p=[]
        for s in p1:
            p.append(max([r[i] for i in s])[1])
        for i in p2:
            if i not in p:
                r[i][2]=len(p)+1
        if len(p)==1:
            r[p[0]][2]=1
            break
    s=''
    for i in range(n-1):
        s+=str(r[i][2])
        s+=' '
    s+=str(r[-1][2])
    print(s) 
这题的难点在于理解题意，一开始我很不能理解为什么比赛4轮，排名中会出现5
后来才明白排名是晋级人数+1
就像学校分数排名，有两个人分数一样排第二名，那么之后的人就排第四名了

发表于 2019-09-12 11:11:15 回复(0)