1.最优清零方案

1.题意描述

给定一个长度为 $N$ 的数列 $A_1,A_2,\cdots ,A_N$ 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一:

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

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

2.输入格式

输入第一行包含两个整数 $N$ 和 $K$ 。
第二行包含 $N$ 个整数$A_1,A_2,\cdots ,A_N$。

3.输出格式

输出一个整数表示答案。

4.样例输入

4 2
1 2 3 4

5.样例输出

6

6.数据范围

$1\le K\le N\le 1000000,0\le A_i\le 1000000。$

7.原题链接

最优清零方案

2.解题思路

比较直观地思考，如果没有操作2，那么总操作次数则是数组的总和。对于答案来说操作2一定是不差于操作1的，为了使操作次数更少，我们应该尽可能多使用操作2。

所以问题转化为我们对数组最多能进行几次操作2？答案即是操作2的次数加上剩下数组的总和。

对于一段区间 $[l,r]$，它能进行操作的次数应当是该区间内的最小值 $mi$，然后我们需要将区间 $[l,r]$ 所有数都减去 $mi$。由于需要去考虑每一个长度为 $K$ 的连续子数组，显然我们需要使用到滑动窗口去解决问题。

从贪心的角度思考，我们从左往右进行窗口滑动，统计操作2可进行的最大次数。

对于每一个长度为 $K$ 的区间 $[l,r]$ 如果我们都手动去遍历得到 $mi$ 以及手动减去$mi$，在极限数据下且$k=n/2$时，复杂度会是$O(n^2)$所以会超时。

考虑如何优化，假设此时枚举的窗口的起点为 $l$，那么终点为$l+k-1$，设区间 $[l,r]$ 的最小值的下标为 $t(t\in [l,r])$，如果按照正常滑动窗口，我们下一次窗口枚举的起点为 $l+1$，但由于操作2要求区间全部数一定大于0。显然 $a[t]$ 在减去$mi$之后的值一定为0，意味着区间内包含下标t一定不可能再进行操作2，我们可以将下一次窗口枚举的起点设为t+1，以此完成优化，减少无效窗口的枚举次数。

值得注意一点的是一个区间$[l,r]$可能同时有多个最小值下标 $t$，我们应当选择最右边的一个。

3.Ac_code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n, k;
void solve()
{
    std::cin >> n >> k;
    std::vector<int> a(n);
    LL ans = 0;
    for (auto&v : a) {
        cin >> v;
    }
    for (int i = 0; i + k - 1 < n; ++i) {
        int t = 0;
        int mi = 1e9;
        for (int j = i; j < i + k; ++j) {
            if (a[j] <= mi) {
                t = j;
                mi = a[j];
            }
        }
        ans += mi;
        for (int j = i; j < i + k; ++j) a[j] -= mi;
        i = t;
    }
    for (auto v : a) ans += v;
    cout << ans << '\n';
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}