第十三届蓝桥杯省赛 最优清零方案题解

题目描述

给定一个长度为N的数列A1, A2, … , AN。
现在小蓝想通过若干次操作将这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一：

1. 选择一个大于0的整数，将它减去1；
2. 选择连续K个大于0的整数，将它们各减去1。
   小蓝最少经过几次操作可以将整个数列清零?

思路

没有采用什么特别的算法，就是用到一些数论的知识点
$$总次数=分段减的次数+一个一个减的次数$$
因为分段减的效率最高，所以能分段减就先分段减，最后数组中剩下的全是离散的数（被0隔开）。这些数只能一个一个减，剩下的数之和就是一个一个减的次数，而分段分段减的次数在减的过程中统计。以[1,2,3,4]，K=2为例：

代码

def lastNotZeroIndex(A,start,end):
    j = start
    for i in range(start,end,1):
        if A[i] == 0:
            j = i
    return j
def bestZero(A,K):
    count = 0
    i = 0
    while i < len(A):
        if i+K <= len(A):
            minElement = min(A[i:i+K])
            if minElement != 0:
                count += minElement
                for j in range(i,i+K,1):
                    A[j] -= minElement
            i = lastNotZeroIndex(A,i,i+K)
        i += 1
    return sum(A) + count
N,K = map(int,input().split(' '))
A = list(map(int,input().split(' ')))
print(bestZero(A,K))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22