网站怎么吸引用户,成都微信小程序开发,网站建设与维护 唐清安,公司推广业务哪个平台好贪心
贪心#xff1a;把整体问题分解成多个步骤#xff0c;在每个步骤都选取当前步骤的最优方案#xff0c;直至所有步骤结束#xff1b;每个步骤不会影响后续步骤核心性质#xff1a;每次采用局部最优#xff0c;最终结果就是全局最优如果题目满足上述核心性质#xf…贪心
贪心把整体问题分解成多个步骤在每个步骤都选取当前步骤的最优方案直至所有步骤结束每个步骤不会影响后续步骤核心性质每次采用局部最优最终结果就是全局最优如果题目满足上述核心性质则可以采用贪心进行求解
如何判断是否能用贪心
最优子结构性质当一个问题的最优解包含子问题的最优解则称之为具有最优子结构性质。贪心性质选择可以通过局部最优的选择得到全局最优
具体问题如何做
经验性积累各种类型的贪心举反例
经典贪心
石子合并问题
石子合并问题每次选择最小的两个
利用堆heapq
题目描述
在很久很久以前有 n n n 个部落居住在平原上依次编号为 1 1 1 到 n n n。第 i i i 个部落的人数为 t i t_i ti。
有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒他能通过谈判来说服部落进行联合。
每次谈判小蓝只能邀请两个部落参加花费的金币数量为两个部落的人数之和谈判的效果是两个部落联合成一个部落人数为原来两个部落的人数之和。
输入描述
输入的第一行包含一个整数 n n n表示部落的数量。
第二行包含 n n n 个正整数依次表示每个部落的人数。
其中 1 ≤ n ≤ 1000 1 ≤ t i ≤ 1 0 4 1≤n≤10001≤t_i≤10^4 1≤n≤10001≤ti≤104。
输出描述
输出一个整数表示最小花费。
import heapq
n int(input())
a list(map(int, input().split()))# 把a转化为堆
heapq.heapify(a)
ans 0
while len(a) 2:x heapq.heappop(a)y heapq.heappop(a)heapq.heappush(a, x y)ans x y
print(ans)分箱问题
每组最多两件价值之和不超过 w w w
尽可能不浪费空间大的和小的凑在一起
题目描述
元旦快到了校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡他要把购来的纪念品根据价格进行分组但每组最多只能包括两件纪念品并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品乐乐希望分组的数目最少。
你的任务是写一个程序找出所有分组方案中分组数最少的一种输出最少的分组数目。
输入描述
第 1 1 1 行包括一个整数 w ( 80 ≤ w ≤ 200 ) w (80≤w≤200) w(80≤w≤200)为每组纪念品价格之和的上限。
第 2 2 2 行为一个整数 n ( 1 ≤ n ≤ 30000 ) n (1≤n≤30000) n(1≤n≤30000)表示购来的纪念品的总件数。
第 3 3 3~ n 2 n2 n2 行每行包含一个正整数 p i ( 5 ≤ p i ≤ w ) p_i (5≤p_i≤w) pi(5≤pi≤w)表示所对应纪念品的价格。
输出描述
输出一行包含一个整数即最少的分组数目。
w int(input())
n int(input())
a []
for i in range(n):a.append(int(input()))a.sort()
l, r 0, n - 1
ans 0while True:if l r:ans 1breakif l r:breakif a[l] a[r] w:ans 1l 1r - 1else:ans 1r - 1
print(ans)翻硬币问题
题目描述
小明正在玩一个翻硬币的游戏。
桌上放着排成一排的若干硬币。我们用 ∗ * ∗ 表示正面用 o o o 表示反面是小写字母不是零。
比如可能情形是 ∗ ∗ o o ∗ ∗ ∗ o o o o **oo***oooo ∗∗oo∗∗∗oooo;
如果同时翻转左边的两个硬币则变为 o o o o ∗ ∗ ∗ o o o o oooo***oooo oooo∗∗∗oooo。
现在小明的问题是如果已知了初始状态和要达到的目标状态每次只能同时翻转相邻的两个硬币,那么对特定的局面最少要翻动多少次呢
我们约定把翻动相邻的两个硬币叫做一步操作。
输入描述
两行等长的字符串分别表示初始状态和要达到的目标状态。
每行的长度1000。
输出描述
一个整数表示最小操作步数。
s list(input())
t list(input())
n len(s)
ans 0
for i in range(n):if s[i] t[i]:continueif s[i 1] *:s[i 1] oelse:s[i 1] *ans 1
print(ans)数组乘积问题
给定两个长度为 n n n 的正整数数组 a a a 和 b b b可以任意排序求 ∑ i 1 n a [ i ] ∗ b [ i ] \sum_{i1}^{n}a[i]*b[i] ∑i1na[i]∗b[i] 的最小值
思路 a a a 从小到大 b b b 从大到小然后对应元素相乘结果最小
参考个人博客贪心
