Python|蓝桥杯进阶第二卷——贪心

欢迎交流学习~~

---

专栏： 蓝桥杯Python组刷题日寄

---

蓝桥杯进阶系列：

🏆 Python | 蓝桥杯进阶第一卷——字符串
🔎 Python | 蓝桥杯进阶第二卷——贪心
💝 Python | 蓝桥杯进阶第三卷——动态规划（待续）
✈️ Python | 蓝桥杯进阶第四卷——图论（待续）
🌞 Python | 蓝桥杯进阶第五卷——数论（待续）
🌠 Python | 蓝桥杯进阶第六卷——递归（待续）
💎 Python | 蓝桥杯进阶第七卷——搜索（待续）

---

🎁 发工资喽

题目：
时间限制：
1s

内存限制：
128MB

题目描述：
作为程序猿，最盼望的日子就是每月的9号了，因为这一天是发工资的日子，养家糊口就靠它了，呵呵
但是对于公司财务处的工作人员来说，这一天则是很忙碌的一天，财务处的小李最近就在考虑一个问题：如果每个员工的工资额都知道，最少需要准备多少张人民币，才能在给每位员工发工资的时候都不用员工找零呢？
这里假设程序猿的工资都是正整数，单位元，人民币一共有 100 元、50 元、10 元、5 元、2 元和 1 元六种。

输入描述：
输入数据包含多个测试实例，每个测试实例的第一行是一个整数n（n<100），表示员工的人数，然后是 n 个员工的工资。
n=0 表示输入的结束，不做处理。

输出描述：
对于每个测试实例输出一个整数 x,表示至少需要准备的人民币张数。每个输出占一行。

样例输入：

3 1 2 3
0

样例输出：
4

---

解题思路

贪心，从面值最大的开始选取，直到满足条件。

参考代码

def func(amount):count1, temp = divmod(amount, 100)count2, temp = divmod(temp, 50)count3, temp = divmod(temp, 10)count4, temp = divmod(temp, 5)count5, temp = divmod(temp, 2)total = count1 + count2 + count3 + count4 + count5 + tempreturn totalwhile True:try:nums = list(map(int, input().split()))n = nums[0]if n != 0:count = 0for i in range(n):count += func(nums[i+1])print(count)except:break

---

🌲 翻硬币

题目：
时间限制：
1s

内存限制：
128MB

题目描述：
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。

输入描述：
两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度 <1000

输出描述：
一个整数，表示最小操作步数。

样例输入：

*o**o***o*** 
*o***o**o*** 

样例输出：
1

---

解题思路

从左到右遍历，如果对应位置两状态不同，就进行翻转，计数。

参考代码

start = list(input())
end = list(input())
L = len(start)
count = 0for i in range(L):if start[i] != end[i]:start[i] = 'o' if start[i] == '*' else '*'start[i+1] = 'o' if start[i+1] == '*' else '*'count += 1print(count)

---

🚀 Huffuman树

题目：
时间限制：
3s

内存限制：
192MB

题目描述：
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。

给出一列数 {pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：

1. 找到 {pi} 中最小的两个数，设为 pa 和 pb，将 pa 和 pb 从 {pi} 中删除掉，然后将它们的和加入到 {pi} 中。这个过程的费用记为 pa + pb。

2. 重复步骤1，直到 {pi} 中只剩下一个数。

在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。

本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列 {pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：

1. 找到 {5, 3, 8, 2, 9} 中最小的两个数，分别是 2 和 3，从 {pi} 中删除它们并将和 5 加入，得到 {5, 8, 9, 5}，费用为 5。

2. 找到 {5, 8, 9, 5} 中最小的两个数，分别是 5 和 5，从 {pi} 中删除它们并将和 10 加入，得到{8, 9, 10}，费用为 10。

3. 找到 {8, 9, 10} 中最小的两个数，分别是 8 和 9，从 {pi} 中删除它们并将和 17 加入，得到 {10, 17}，费用为 17。

4. 找到 {10, 17} 中最小的两个数，分别是 10 和 17，从 {pi} 中删除它们并将和 27 加入，得到 {27}，费用为 27。

5. 现在，数列中只剩下一个数 27，构造过程结束，总费用为 5+10+17+27=59。

输入描述：
输入的第一行包含一个正整数 n（n< =100）。

接下来是 n 个正整数，表示 p0, p1, …, pn-1，每个数不超过 1000。

输出描述：
输出用这些数构造Huffman树的总费用。

样例输入：

5 
5 3 8 2 9

样例输出：
59

---

解题思路

排序后循环 n-1 次，每次选出前两个（最小值），计算其和后，再加入列表中，并将这两个最小值删除。

参考代码

n = int(input())
nums = list(map(int, input().split()))
res = 0
nums.sort()for i in range(n-1):total = nums[0] + nums[1]nums.append(total)res += totalnums.pop(0)nums.pop(0)nums.sort()
print(res)

---

💡 打水问题

题目：
时间限制：
1s

内存限制：
128MB

题目描述：
N 个人要打水，有 M 个水龙头，第 i 个人打水所需时间为 Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。

提示：
一种最佳打水方案是，将 N 个人按照 Ti 从小到大的顺序依次分配到 M 个龙头打水。
例如样例中，Ti 从小到大排序为 1，2，3，4，5，6，7，将他们依次分配到 3 个龙头，则去龙头一打水的为1，4，7；去龙头二打水的为2, 5；去第三个龙头打水的为 3, 6。
第一个龙头打水的人总等待时间 = 0 + 1 + (1 + 4) = 6
第二个龙头打水的人总等待时间 = 0 + 2 = 2
第三个龙头打水的人总等待时间 = 0 + 3 = 3
所以总的等待时间 = 6 + 2 + 3 = 11

输入描述：
第一行两个正整数 N M 接下来一行 N 个正整数 Ti。
N,M< =1000，Ti< =1000

输出描述：
最小的等待时间之和。（不需要输出具体的安排方案）

样例输入：

7 3
3 6 1 4 2 5 7

样例输出：
11

---

解题思路

排序后直接计算。

参考代码

n, m = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
res = 0
# 只有 n-m 个要等待
for i in range(0, n-m):t[i+m] += t[i]res += t[i]
print(res)

---

🍞 排队打水问题

题目：
时间限制：
1s

内存限制：
128MB

题目描述：
有 n 个人排队到 r 个水龙头去打水，他们装满水桶的时间 t1、t2………..tn 为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

输入描述：
第一行 n，r (n< =500,r< =75)
第二行为 n 个人打水所用的时间 Ti (Ti< =100)；

数据规模和约定
其中 80% 的数据保证 n< =10

输出描述：
最少的花费时间

样例输入：

3 2
1 2 3

样例输出：

7

---

解题思路

假设多了 m 个打水时间为 0 的人，此时需要可以转化为前一个问题，此时有 n 个需要等待的人。

参考代码

n, m = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
res = 0
# 要计算总花费时间，我们可以假设多了 m 个打水时间为0的人
t += [0 for i in range(m)]
# 即计算n个等待的人
for i in range(0, n):t[i+m] += t[i]res += t[i]
print(res)

---