题目描述

问题描述

给定一个长度为 N 的数列 A1,A2,⋯ ,AN。现在小蓝想通过若干次操作将这个数列中每个数字清零。

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

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

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

输入格式

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

第二行包含 N 个整数 A1,A2,⋯ ,AN。

输出格式

输出一个整数表示答案。

样例输入

4 2
1 2 3 4

样例输出

6

评测用例规模与约定

• 对于 20% 的评测用例, 1≤K≤N≤10 。
• 对于 40% 的评测用例, 1≤K≤N≤100 。
• 对于 50% 的评测用例, 1≤K≤N≤1000 。
• 对于 60% 的评测用例, 1≤K≤N≤10000 。
• 对于 70% 的评测用例, 1≤K≤N≤100000 。
• 对于所有评测用例, 1≤K≤N≤1000000,0≤Ai≤1000000 。

运行限制

• 最大运行时间：15s
• 最大运行内存: 512M

题解

对于两个操作，2 操作一次性可以减小多个数的值，因此我们优先考虑使用 2 操作，当无法进行 2 操作的时候再进行1操作，此时1 操作最终结果就是当前数组所有元素之和

我们枚举一个L，每次判断区间【L，L+k-1】的最小值num，num不是0 的话我们就将区间里面所有数字全部减去 num，并将答案加上 num 就行，但是这样时间复杂度很高，考虑使用线段树维护区间最小值

java 代码

import java.util.*;
import java.io.*;

public class Main {
    static final int maxn = 1000005 << 2;
    static int[] z = new int[maxn], tag = new int[maxn], a = new int[maxn];

    static int num = 0, n, k;

    static void update(int rt) {
        z[rt] = Math.min(z[rt << 1], z[rt << 1 | 1]);
    }

    static void build(int l, int r, int rt) {
        if (l == r) {
            z[rt] = a[++num];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);
        update(rt);
    }

    static void add(int rt, int x) {
        z[rt] += x;
        tag[rt] += x;
    }

    static void push_down(int rt) {
        if (tag[rt] != 0) {
            add(rt << 1, tag[rt]);
            add(rt << 1 | 1, tag[rt]);
            tag[rt] = 0;
        }
    }

    static int find(int l, int r, int rt, int findl, int findr) {
        if (l == findl && r == findr)
            return z[rt];
        int mid = (l + r) >> 1;
        push_down(rt);

        if (findl <= mid) {
            if (findr > mid)
                return Math.min(find(l, mid, rt << 1, findl, mid), find(mid + 1, r, rt << 1 | 1, mid + 1, findr));
            return find(l, mid, rt << 1, findl, findr);
        }
        return find(mid + 1, r, rt << 1 | 1, findl, findr);
    }

    static void modify(int l, int r, int rt, int findl, int findr, int x) {
        if (l == findl && r == findr) {
            add(rt, x);
            return;
        }
        int mid = (l + r) >> 1;
        push_down(rt);
        if (findl <= mid) {
            if (findr > mid) {
                modify(l, mid, rt << 1, findl, mid, x);
                modify(mid + 1, r, rt << 1 | 1, mid + 1, findr, x);
            } else
                modify(l, mid, rt << 1, findl, findr, x);
        } else
            modify(mid + 1, r, rt << 1 | 1, findl, findr, x);
        update(rt);
    }

    static Read st = new Read();

    public static void main(String[] args) throws Exception {
        n = st.nextInt();
        k = st.nextInt();
        for (int i = 1; i <= n; i++) {
            a[i] = st.nextInt();
        }
        build(1, n, 1);
        long ans = 0;
        for (int l = 1; l + k - 1 <= n; l++) {
            int r = l + k - 1;
            int num = find(1, n, 1, l, r);
            if (num != 0) {
                modify(1, n, 1, l, r, -num);
                ans += num;
            }
        }

        for (int i = 1; i <= n; i++) {
            ans += find(1, n, 1, i, i);
        }
        System.out.println(ans);
    }

}

class Read {
    StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public int nextInt() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }
}

END