第十三届蓝桥杯省赛 Java A 组 I 题、Python A 组 I 题、Python B 组 J 题——最优清零方案（AC）
1.最优清零方案
1.题意描述
给定一个长度为
N
N
N 的数列
A
1
,
A
2
,
⋯
,
A
N
A_1,A_2,⋯,A_N
A1,A2,⋯,AN 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一:
- 选择一个大于 0 的整数, 将它减去 1 ;
- 选择连续 K K K 个大于 0 的整数, 将它们各减去 1 。
小蓝最少经过几次操作可以将整个数列清零?
2.输入格式
输入第一行包含两个整数
N
N
N 和
K
K
K 。
第二行包含
N
N
N 个整数
A
1
,
A
2
,
⋯
,
A
N
A_1,A_2,⋯,A_N
A1,A2,⋯,AN。
3.输出格式
输出一个整数表示答案。
4.样例输入
4 2
1 2 3 4
5.样例输出
6
6.数据范围
1 ≤ K ≤ N ≤ 1000000 , 0 ≤ A i ≤ 1000000 。 1≤K≤N≤1000000,0≤A_i ≤1000000 。 1≤K≤N≤1000000,0≤Ai≤1000000。
7.原题链接
最优清零方案
2.解题思路
比较直观地思考，如果没有操作2，那么总操作次数则是数组的总和。对于答案来说操作2一定是不差于操作1的，为了使操作次数更少，我们应该尽可能多使用操作2。
所以问题转化为我们对数组最多能进行几次操作2？答案即是操作2的次数加上剩下数组的总和。
对于一段区间 [ l , r ] [l,r] [l,r]，它能进行操作的次数应当是该区间内的最小值 m i mi mi，然后我们需要将区间 [ l , r ] [l,r] [l,r] 所有数都减去 m i mi mi。由于需要去考虑每一个长度为 K K K 的连续子数组，显然我们需要使用到滑动窗口去解决问题。
从贪心的角度思考，我们从左往右进行窗口滑动，统计操作2可进行的最大次数。
对于每一个长度为 K K K 的区间 [ l , r ] [l,r] [l,r] 如果我们都手动去遍历得到 m i mi mi 以及手动减去 m i mi mi，在极限数据下且 k = n / 2 k=n/2 k=n/2时，复杂度会是 O ( n 2 ) O(n^2) O(n2)所以会超时。
考虑如何优化，假设此时枚举的窗口的起点为
l
l
l，那么终点为
l
+
k
−
1
l+k-1
l+k−1，设区间
[
l
,
r
]
[l,r]
[l,r] 的最小值的下标为
t
(
t
∈
[
l
,
r
]
)
t(t\in[l,r])
t(t∈[l,r])，如果按照正常滑动窗口，我们下一次窗口枚举的起点为
l
+
1
l+1
l+1，但由于操作2要求区间全部数一定大于0。显然
a
[
t
]
a[t]
a[t] 在减去
m
i
mi
mi之后的值一定为0，意味着区间内包含下标t一定不可能再进行操作2，我们可以将下一次窗口枚举的起点设为t+1，以此完成优化，减少无效窗口的枚举次数。
值得注意一点的是一个区间 [ l , r ] [l,r] [l,r]可能同时有多个最小值下标 t t 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 + k - 1;
}
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;
}