首页 > 试题广场 >

糖果分配

[编程题]糖果分配

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

假设你是一位很有爱的幼儿园老师，想要给幼儿园的小朋友们一些小糖果。但是，每个孩子最多只能给一块糖果。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的糖果的最小尺寸；并且每块糖果 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个糖果 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：
你可以假设胃口值为正。
一个小朋友最多只能拥有一块糖果。

输入描述:

第一行输入每个孩子的胃口值

第二行输入每个糖果的尺寸

孩子数和糖果数不超过1000

输出描述:

能满足孩子数量的最大值

示例1

输入

1 2 3
1 1

输出

算法知识视频讲解

Python3

TS9527

排序+贪心

class MainActivity:

    def main(self):
        # Read the data
        children = list(map(int, filter(lambda x: len(x) > 0, input().split(' '))))
        candies = list(map(int, filter(lambda x: len(x) > 0, input().split(' '))))
        # Initialiation
        result = 0
        children.sort(reverse=True)
        candies.sort(reverse=True)
        childPtr = 0
        # Traverse
        for candy in candies:
            while childPtr < len(children) and candy < children[childPtr]:
                childPtr += 1
            if childPtr >= len(children):
                break
            if candy >= children[childPtr]:
                result += 1
                childPtr += 1
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-26 15:56:06 回复(0)