题目描述
小明是个鹅卵石收藏者，从小到大他一共收藏了 n块鹅卵石，编号分别为 1∼n，价值分别为 。
a1，a2，⋯,an
这天他乘船准备去往蓝桥王国，然而天有不测风云，小明所在的海域下起了暴雨。
很快小明船上的积水越来越多，为了防止沉船，小明不得不选择若干块他收藏的鹅卵石丢弃。
小明制定了一套名为m计划的选择方案，其内容如下：
- 对于任意区间 [i,i + m - 1][i,i+m−1]丢弃价值最小的鹅卵石i\in[1,n-m+1]i∈[1,n−m+1]。
- 对于一块鹅卵石，它在 m 计划中是可以被丢弃多次的。
请你输出将被小明丢弃的鹅卵石的价值。
输入描述
输入第 1 行包含两个正整数 n,m
接下来一行包含 n 个正整 a1,a2,⋯,an，表示鹅卵石的价值。
1≤m≤n≤5×105，0\leq a_i\leq 10^90≤ai≤109
输出描述
输出共 n−m+1 行，每行输出一个整数
第 ii 行输出整数的含义为 ai,ai+1,⋯,ai+m−1 的最小值。
输入输出样例
示例 1
输入
1. 5 3 2. 5 3 2 4 1
输出
1. 2 2. 2 3. 1
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
思路一：
(6条消息) 蓝桥杯-区间最大值-python_晓宜的博客-CSDN博客
总的来说是先通过动态规划找出以i为起始点，2^j为区间长度的最小值，因为题目中限定了长度为m，我们需要找到两个覆盖m的区间，其长度为k
代码1
1. from math import * 2. n,m=map(int,input().split()) 3. b=list(map(int,input().split())) 4. max=100001 5. dp=[[0]*40 for row in range(max)] 6. a=[0]*max 7. for i in range(n): 8. dp[i+1][0]=b[i] 9. k=int(log2(m)) 10. 11. for j in range(1,k+1): 12. for i in range(1,n+2-(1<<j)): 13. dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]) 14. 15. for i in range(1,n-m+2): 16. print(min(dp[i][k],dp[i+m-(1<<k)][k]))
思路二：
对a数组进行遍历，在滑动窗口【i,i+m-1】内寻找最小值，为了避免超时进行剪枝，设置变量flag,如果当前的最小值发生变动，则flag设置成1,到下一个a数组时要遍历【i,i+m-1】寻找新的最小值。如果当前最小值不发生变动，则flag设置成0，因为等于min的a数组的值只可能在此时的a[i]后面，所以只需要比较当前min与新加入的哪个数即可。输出此区间的最小值。
代码二：
1. n,m=map(int,input().split()) 2. b=list(map(int,input().split())) 3. a=[0]*50000 4. for i in range(n): 5. a[i+1]=b[i] 6. flag=1 7. 8. for i in range(1,n+2-m): 9. if flag: 10. min=a[i] 11. for j in range(i,i+m): 12. if a[j]<min: 13. min=a[j] 14. else: 15. if min>a[i+m-1]: 16. min=a[i+m-1] 17. 18. if min==a[i]: 19. flag=1 20. else: 21. flag=0 22. 23. print(min)
