第十三届蓝桥杯省赛 Java A 组 I 题、Python A 组 I 题、Python B 组 J 题——最优清零方案（AC）

妖狐艹你老母 2023-09-29 18:35 10阅读 0赞

## 1.最优清零方案 ##

### 1.题意描述 ###

给定一个长度为  N N N 的数列  A 1 , A 2 , ⋯ , A N A\_1,A\_2,⋯,A\_N A1,A2,⋯,AN 。现在小蓝想通过若干次操作将 这个数列中每个数字清零。  
每次操作小蓝可以选择以下两种之一:

1.  选择一个大于 0 的整数, 将它减去 1 ;
2.  选择连续  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.数据范围 ###

1 ≤ K ≤ N ≤ 1000000 , 0 ≤ A i ≤ 1000000 。 1≤K≤N≤1000000,0≤A\_i ≤1000000 。 1≤K≤N≤1000000,0≤Ai≤1000000。

### 7.原题链接 ###

[最优清零方案][Link 1]

## 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;
        }
        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;
    }

[Link 1]: https://www.lanqiao.cn/problems/2138/learning/