【蓝桥杯青少组】第十五届省赛python(2024)

选择题做得飞快。编程题被绊住了...
第四题 熟悉 等差数列求和公式即可，无需赘述
第五题 果然是贪心算法，之前强化训练了一天，看来效果还是不够。

题目简述

浇水
n棵植物编号i=1-n，所需浇水w[i]
每次连续浇L棵，每棵1份水，重复浇多余的排水。
问，最少需要浇多少次，共排水多少量？
输入：
n=4; L=3; w=[1,1,3,2]
输出
3,2

思路

 贪心算法
# 先找到最高max(w)
# 再算前后L个范围内连续L个w[j]之和，取最高段[ind,ind+L]浇水， 
# 因一，最高优先，早晚要浇
#    二，浇水每次L,需水固定，最少浇水次数->最少浇水量->最少排水量->sum(range(ind,ind+L))最大

代码

import random
n=random.randint(30,50);L=random.randint(n//5,n//4+1)
w=[random.randint(1,10) for _ in range(n)]
# n=4; L=3; w=[1,1,3,2] # 输入。输出应为 3,2
print(n,L); print(w,"\n")

# 贪心算法
# 先找到最高max(w)
# 再算前后L个范围内连续L个之和最高， 
# 因一，最高优先，早晚要浇
#	二，浇水每次L,需水固定，最少浇水次数->最少浇水量->最少排水量->sum(range(ind,ind+L))最大
need=sum(w)
if n<=L:
	cnt=max(w); ma=0  # 直接全浇水
else:
	cnt=0; ma=max(w)
while(ma>0):
	i=w.index(ma) # 最高点的序号
	# 找到包括i的浇水范围 range(iB,iE)
	iB=i-L+1 if i-L+1>0 else 0 
	iE=i+L if i+L<n else n 
	# 计算可用范围段，连续L个数的sum
	ws=[sum(w[j:j+L]) for j in range(iB,iE-L+1) if j+L<=n]
	# 取max(sum)段浇水，注意len(ws)的情况，即
	ind=ws.index(max(ws))+iB if len(ws)>0 else iE-L
	for j in range(ind,ind+L): w[j]=w[j]-1 if w[j]>0 else 0
	cnt+=1; ma=max(w); print(cnt,w)
print(cnt,cnt*L-need)

小结

回顾这类贪心算法问题

原始版：鸡兔同笼，假设所有头都是鸡的，多一只兔，就多2条腿

基础版：吃奶酪，甲乙口味不同，吃不同奶酪给分不同，已知a吃k个，求最高分？
假设都给乙吃，然后降序排 a[i]-b[i], 取前k个，累加分差。

本题应该算是进阶版，思路一以贯之，先找个参照点比如max(w)，然后sort排水量或等价的sum(ws)，然后执行动作(浇水)，然后在控制条件(max(w)==0)未满足时继续下一轮。

终极版还可以不均匀浇水（类似扇形喷嘴或者出水口离进水口距离不同而出水量不同）等。