蓝桥杯-m计划-python

蓝桥杯-m计划-python 题目描述

小明是个鹅卵石收藏者，从小到大他一共收藏了 n块鹅卵石，编号分别为 1∼n，价值分别为 。

a1​，a2​，⋯,an​

这天他乘船准备去往蓝桥王国，然而天有不测风云，小明所在的海域下起了暴雨。

很快小明船上的积水越来越多，为了防止沉船，小明不得不选择若干块他收藏的鹅卵石丢弃。

小明制定了一套名为m计划的选择方案，其内容如下：

对于任意区间 [i,i + m - 1][i,i+m−1]丢弃价值最小的鹅卵石iin[1,n-m+1]i∈[1,n−m+1]。对于一块鹅卵石，它在 m 计划中是可以被丢弃多次的。

请你输出将被小明丢弃的鹅卵石的价值。

输入描述

输入第 1 行包含两个正整数 n,m

接下来一行包含 n 个正整 a1​,a2​,⋯,an​，表示鹅卵石的价值。

1≤m≤n≤5×105，0leq a_ileq 10^90≤ai​≤109

输出描述

输出共 n−m+1 行，每行输出一个整数

第 ii 行输出整数的含义为 ai​,ai+1​,⋯,ai+m−1​ 的最小值。

输入输出样例

示例 1

输入

5 3
5 3 2 4 1

输出

2
2
1

运行限制

最大运行时间：1s最大运行内存: 256M

思路一：

(6条消息) 蓝桥杯-区间最大值-python_晓宜的博客-CSDN博客

总的来说是先通过动态规划找出以i为起始点，2^j为区间长度的最小值，因为题目中限定了长度为m，我们需要找到两个覆盖m的区间，其长度为k

代码1

from math import *
n,m=map(int,input().split())
b=list(map(int,input().split()))
max=100001
dp=[[0]*40 for row in range(max)]
a=[0]*max
for i in range(n):
  dp[i+1][0]=b[i]
k=int(log2(m))

for j in range(1,k+1):
  for i in range(1,n+2-(1< 
思路二：
 
对a数组进行遍历，在滑动窗口【i,i+m-1】内寻找最小值，为了避免超时进行剪枝，设置变量flag,如果当前的最小值发生变动，则flag设置成1,到下一个a数组时要遍历【i,i+m-1】寻找新的最小值。如果当前最小值不发生变动，则flag设置成0，因为等于min的a数组的值只可能在此时的a[i]后面，所以只需要比较当前min与新加入的哪个数即可。输出此区间的最小值。
 
代码二：
 
n,m=map(int,input().split())
b=list(map(int,input().split()))
a=[0]*50000
for i in range(n):
  a[i+1]=b[i]
flag=1

for i in range(1,n+2-m):
  if flag:
    min=a[i]
    for j in range(i,i+m):
      if a[j]a[i+m-1]:
      min=a[i+m-1]
  
  if min==a[i]:
    flag=1
  else:
    flag=0
  
  print(min)
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5720809.html