建设网站制作实训报告,适合个人做的网站,保险网站建设公司,网络规划与优化技术学什么欢迎交流学习~~ 专栏#xff1a; 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列#xff1a; #x1f3c6; Python | 蓝桥杯进阶第一卷——字符串 #x1f50e; Python | 蓝桥杯进阶第二卷——贪心 #x1f49d; Python | 蓝桥杯进阶第三卷——动态规划#xff08;待续#xf… 欢迎交流学习~~ 专栏 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列 Python | 蓝桥杯进阶第一卷——字符串 Python | 蓝桥杯进阶第二卷——贪心 Python | 蓝桥杯进阶第三卷——动态规划待续 ✈️ Python | 蓝桥杯进阶第四卷——图论待续 Python | 蓝桥杯进阶第五卷——数论待续 Python | 蓝桥杯进阶第六卷——递归待续 Python | 蓝桥杯进阶第七卷——搜索待续 Python|蓝桥杯进阶第二卷——贪心 发工资喽 翻硬币 Huffuman树 打水问题 排队打水问题发工资喽
题目 时间限制 1s
内存限制 128MB
题目描述 作为程序猿最盼望的日子就是每月的9号了因为这一天是发工资的日子养家糊口就靠它了呵呵 但是对于公司财务处的工作人员来说这一天则是很忙碌的一天财务处的小李最近就在考虑一个问题如果每个员工的工资额都知道最少需要准备多少张人民币才能在给每位员工发工资的时候都不用员工找零呢 这里假设程序猿的工资都是正整数单位元人民币一共有 100 元、50 元、10 元、5 元、2 元和 1 元六种。
输入描述 输入数据包含多个测试实例每个测试实例的第一行是一个整数nn100表示员工的人数然后是 n 个员工的工资。 n0 表示输入的结束不做处理。
输出描述 对于每个测试实例输出一个整数 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[i1])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[i1] o if start[i1] * else *count 1print(count)Huffuman树
题目 时间限制 3s
内存限制 192MB
题目描述 Huffman树在编码中有着广泛的应用。在这里我们只关心Huffman树的构造过程。
给出一列数 {pi}{p0, p1, …, pn-1}用这列数构造Huffman树的过程如下 找到 {pi} 中最小的两个数设为 pa 和 pb将 pa 和 pb 从 {pi} 中删除掉然后将它们的和加入到 {pi} 中。这个过程的费用记为 pa pb。 重复步骤1直到 {pi} 中只剩下一个数。
在上面的操作过程中把所有的费用相加就得到了构造Huffman树的总费用。
本题任务对于给定的一个数列现在请你求出用该数列构造Huffman树的总费用。
例如对于数列 {pi}{5, 3, 8, 2, 9}Huffman树的构造过程如下 找到 {5, 3, 8, 2, 9} 中最小的两个数分别是 2 和 3从 {pi} 中删除它们并将和 5 加入得到 {5, 8, 9, 5}费用为 5。 找到 {5, 8, 9, 5} 中最小的两个数分别是 5 和 5从 {pi} 中删除它们并将和 10 加入得到{8, 9, 10}费用为 10。 找到 {8, 9, 10} 中最小的两个数分别是 8 和 9从 {pi} 中删除它们并将和 17 加入得到 {10, 17}费用为 17。 找到 {10, 17} 中最小的两个数分别是 10 和 17从 {pi} 中删除它们并将和 27 加入得到 {27}费用为 27。 现在数列中只剩下一个数 27构造过程结束总费用为 510172759。
输入描述 输入的第一行包含一个正整数 nn 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 从小到大排序为 1234567将他们依次分配到 3 个龙头则去龙头一打水的为147去龙头二打水的为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 1000Ti 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[im] t[i]res t[i]
print(res)排队打水问题
题目 时间限制 1s
内存限制 128MB
题目描述 有 n 个人排队到 r 个水龙头去打水他们装满水桶的时间 t1、t2………..tn 为整数且各不相等应如何安排他们的打水顺序才能使他们总共花费的时间最少
输入描述 第一行 nr (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[im] t[i]res t[i]
print(res)
