欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯每日一题(32)分配口罩(python)

程序员文章站 2022-03-06 21:00:34
...

Topic

试题 C: 分配口罩

【问题描述】

某市市长获得了若干批口罩,给定每批口罩的数量,市长要把口罩分配给市内的2所医院。
masks = [9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200, 4175600, 6309600, 5865200, 6604400, 4635000, 10663400, 8087200, 4554000]
由于物流限制,每一批口罩只能全部分配给其中一家医院。
市长希望2所医院获得的口罩总数之差越小越好。
请你计算这个差最小是多少?

【答案提交】

这是一道结果填空题,你只需要算出结果后提交即可。
本题的结果为一个 整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

Solution

可以把本题看作一个简单的dfs问题

本题求最小值
可以先把ans设置乘近似无穷大0x3f3f3f3f
这里可以把ans设置成一个列表作为全局变量

对于masks中的值有两种情况
一种为加入医院h_1
一种为加入医院h_2

在递归加入时同时需要记录加入次数cou
方便再下一次将下一个masks中的值加入
和计算已经加入的值

对于已经加入完成(cou = 15)的情况
可以将每次的差值与原值对比并记录最小的一个

最后全部方法递归完成后输出的ans就是结果

Code

masks = [9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200, 4175600, 6309600, 5865200, 6604400, 4635000,
         10663400, 8087200, 4554000]
ans = [0x3f3f3f3f]


def dfs(cou, h_1, h_2):
    if cou == 15:
        ans[0] = min(ans[0], abs(h_1 - h_2))
        return

    dfs(cou + 1, h_1 + masks[cou], h_2)
    dfs(cou + 1, h_1, h_2 + masks[cou])


dfs(0, 0, 0)
print(ans)

Answer

2400