首页 > 试题广场 >

小熊吃糖

[编程题]小熊吃糖

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

有n只小熊，他们有着各不相同的战斗力。每次他们吃糖时，会按照战斗力来排，战斗力高的小熊拥有优先选择权。前面的小熊吃饱了，后面的小熊才能吃。每只小熊有一个饥饿值，每次进食的时候，小熊们会选择最大的能填饱自己当前饥饿值的那颗糖来吃，可能吃完没饱会重复上述过程，但不会选择吃撑。

现在给出n只小熊的战斗力和饥饿值，并且给出m颗糖能填饱的饥饿值。

求所有小熊进食完之后，每只小熊剩余的饥饿值。

输入描述:

第一行两个正整数n和m，分别表示小熊数量和糖的数量。（n <= 10, m <= 100）
第二行m个正整数，每个表示着颗糖能填充的饥饿值。
接下来的n行，每行2个正整数，分别代表每只小熊的战斗力和当前饥饿值。
题目中所有输入的数值小于等于100。

输出描述:

输出n行，每行一个整数，代表每只小熊剩余的饥饿值。

示例1

输入

2 5
5 6 10 20 30
4 34
3 35

输出

4
0

说明

第一只小熊吃了第5颗糖
第二只小熊吃了第4颗糖
第二只小熊吃了第3颗糖
第二只小熊吃了第1颗糖

算法知识视频讲解

Python3

波千鸟

n, m = list(map(int, input().split(" ")))
warh = {}

h = list(map(int, input().split(" ")))
    
for i in range(n):
    warh[i] = list(map(int, input().split(" ")))

ls = sorted(warh.items(), key=lambda x:x[1], reverse=True)
# 按战斗值排序后，去掉战斗值，第一列为第几只熊，第二列为饥饿值
wh = [[] for _ in range(n)]
for i in range(n):
    wh[i] = [ls[i][0], ls[i][1][1]]

h.sort(reverse=True)

res = [0] * n
eat = [False] * m

for i in range(n):
    for j in range(m):
        if not eat[j]:    # 糖不能重复吃
            if wh[i][1] - h[j] > 0:
                wh[i][1] -= h[j]
                eat[j] = True
            elif wh[i][1] - h[j] == 0:
                wh[i][1] = 0
                eat[j] = True
                break
    else:
        res[wh[i][0]] = wh[i][1]
for i in range(n):
    print(res[i])

发表于 2021-08-18 15:23:21 回复(0)