【Codeforces】1661D Progressions Covering 题解

题目大意

给定包含 $n$ 个数的数组 $a, b$，其中 $a$ 初始均为 $0$。我们每次操作可以在 $a$ 中选择一段连续的数，使其每个数分别加上 $1, 2, 3, 4, 5, \ldots, k$。

给定 $a, b, k\ (1 \le k \le n \le 3 \cdot 10^5,\ 1 \le b_i \le 10^{12})$，要求 $a_i \ge b_i\ (1 \le i \le n)$，求最少操作次数。

题目链接

思路

首先我们需要知道从哪一边进行操作。为了方便，我们直接在数组 $b$ 上进行减操作。

如果我们从左边开始，进行了一些操作后，$b$ 数组是 $[0, 2, \ldots]$，那么我们就无法判断，最优情况是从第一位开始减，还是从第二位开始减去。

如果我们从后面开始计算，那么为了使得第 $n$ 位减到 $0$，我们肯定要选择以 $n$ 为结尾的子序列，除此之外没有另外的操作。减掉之后，对于第 $n-1$ 位来说，这就是一个相同的子问题。

那么问题就在于我们怎么减去，因为直接减会TLE :(

对于当前位置 $p$（$p \ge k$），前面需要减去的数就会递减。我们令 $sum$ 是当前所有操作累积对位置 $p$ 的贡献，$cnt$ 是当前每步的递减量。初始状态下 $sum = k$，然后前面的数就需要依次减去 $sum -= 1, sum -= 1, sum -= 1\ldots$，我们用 $cnt$ 表示这个递减量。只进行了一次减去操作的话，$cnt = 1$。

因为减去的序列长度是 $k$，所以 $cnt$ 在被减去 $k$ 次后，就需要减去 $1$。所以我们用 $cl[i]$ 数组表示在第 $i$ 个位置 $cnt$ 需要减去的数量。

那么在 $p$ 位置如果需要进行 $x$ 次减去操作，那么 $sum += x \cdot k,\ cnt += x$。在 $p - k$ 位置之后，就不要再考虑这个减去操作了，所以 $cl[p - k] += x$。

另外需要注意的就是，到数组前面时，长度可能不到 $k$，所以就需要用当前序列长度代替 $k$。

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 3e5 + 7;

int n, k;
long long b[maxN], cl[maxN], ans;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%lld", &b[i]);
    long long sum = 0, cnt = 0;
    for(int i = n; i >= 1; --i) {
        sum -= cnt;
        cnt -= cl[i];
        b[i] -= sum;
        if(b[i] > 0) {
            int now = min(i, k);
            long long nd = b[i] / now + (b[i] % now == 0 ? 0 : 1);
            sum += nd * now;
            cnt += nd;
            ans += nd;
            if(i - now >= 1)
                cl[i - now] += nd;
        }
    }
    printf("%lld\n", ans);
    return 0;
}