线段树：最优清零方案

最优清零方案

问题描述

给定一个长度为 $N$ 的数列 $A_{1}, A_{2}, \cdots, A_{N}$ 。现在小蓝想通过若干次操作将这个数列中每个数字清零。

每次操作小蓝可以选择以下两种之一:

选择一个大于 0 的整数, 将它减去 1 ;
选择连续 $K$ 个大于 0 的整数, 将它们各减去 1 。

小蓝最少经过几次操作可以将整个数列清零?

输入格式

输入第一行包含两个整数 $N$ 和 $K$ 。

第二行包含 $N$ 个整数 $A_{1}, A_{2}, \cdots, A_{N}$ 。

输出格式

输出一个整数表示答案。

样例输入

4 2
1 2 3 4

样例输出

评测用例规模与约定

对于 $\\%$ 的评测用例, $\leq K \leq N \leq 10$ 。

对于 $\\%$ 的评测用例, $\leq K \leq N \leq 100$ 。

对于 $\\%$ 的评测用例, $\leq K \leq N \leq 1000$ 。

对于 $\\%$ 的评测用例, $\leq K \leq N \leq 10000$ 。

对于 $\\%$ 的评测用例, $\leq K \leq N \leq 100000$ 。

对于所有评测用例, $\leq K \leq N \leq 1000000,0 \leq A_{i} \leq 1000000$ 。

解题思路

分析
1、每次只能对某个数字减去 $1$ ，或者对长度为 $K$ 的序列减去1
——单点修改、区间修改

2、从最左端出发，即区间 $[1, K]$ ，如果对该区间进行减法，则最多只能减去该区间的最小值。如果区间最小值为0，则无法进行减法，那也就是第一个数字只能一次一次消去。
——如何选择单点修改和区间修改

根据上述分析，我们只需要从左往右枚举左端点 $l$ ，此时可以处理的区间为 $[l, l + k - 1]$ ，需要求出区间最小值 $mi$ ：

如果 $mi == 0$ ，答案加上此时的 $a [l]$ ，说明无法以该起点进行区间消除，只能单个消除。
如果 $mi\neq0$ ，答案加上 $mi$ ，然后对区间 $[l, l + k - 1]$ 进行区间减法，统一减去 $mi$ 。然后再加上此时的 $a [l]$ ，因为此时剩下的 $a [l]$ 部分也只能单个消除。

AC_Code（Python）

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
maxn = 1000000 + 10
tree_mi = [0] * (maxn * 4)
tree_add = [0] * (maxn * 4)

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [0, *a]

#线段树模板
#利用左右儿子信息更新节点o
def push_up(o):
    tree_mi[o] = min(tree_mi[o << 1], tree_mi[o << 1 | 1])

#利用节点o的lazy标记add更新左右儿子
def push_down(o):
    if tree_add[o] != 0:
        tree_add[o << 1] += tree_add[o]
        tree_mi[o << 1] += tree_add[o]
        tree_add[o << 1 | 1] += tree_add[o]
        tree_mi[o << 1 | 1] += tree_add[o]
        tree_add[o] = 0

#建树
def build(o, l, r):
    tree_add[o] = 0
    if l == r:
        tree_mi[o] = a[l]
        return
    mid = (l + r) >> 1
    build(o << 1, l, mid)
    build(o << 1 | 1, mid + 1, r)
    push_up(o)

#查询区间[L,R]的最小值
def query(o, l, r, L, R):
    if L <= l and r <= R:
        return tree_mi[o]
    push_down(o);
    mid = (l + r) >> 1
    ans = 1000000000;
    if L <= mid:
        ans = min(ans, query(o << 1, l, mid, L, R))
    if R > mid:
        ans = min(ans, query(o << 1 | 1, mid + 1, r, L, R))
    return ans

#区间更新[L,R]统一加上val
def update(o, l, r, L, R, val):
    if L <= l and r <= R:
        tree_mi[o] += val
        tree_add[o] += val
        return
    push_down(o);
    mid = (l + r) >> 1
    if L <= mid:
        update(o << 1, l, mid, L, R, val)
    if R > mid:
        update(o << 1 | 1, mid + 1, r, L, R, val)
    push_up(o);


build(1, 1, n)
ans = 0
for i in range(1, n - k + 2):
    #查询区间[i, i+k-1]的最小值
    mi = query(1, 1, n, i, i + k - 1)
    if mi == 0:                     #无法进行区间消除
        #res表示当前的a[i]
        res = query(1, 1, n, i, i)
        #把当前的a[i]置为0
        update(1, 1, n, i, i, -res)
        ans += res
    else:
        ans += mi
        #区间消除
        update(1, 1, n, i, i + k - 1, -mi)
        #res表示当前的a[i]
        res = query(1, 1, n, i, i)
        #把当前的a[i]置为0
        update(1, 1, n, i, i, -res)
        ans += res
for i in range(n - k + 2, n + 1):
    ans += query(1, 1, n, i, i)
print(ans)