【Codeforces】1661D Progressions Covering 题解

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

给定 a , b , k ( 1 ≤ k ≤ n ≤ 3 ∗ 1 0 5 , 1 ≤ b i ≤ ≤ 1 0 12 ) a,b,k(1 le k le n le 3 * 10^5, 1 le b_i le le 10^{12}) a,b,k(1≤k≤n≤3∗105,1≤bi​≤≤1012),求使得 a i ≥ b i ( 1 ≤ i ≤ n ) a_i ge b_i (1 le i le n) ai​≥bi​(1≤i≤n),的最小操作次数

题目链接

首先我们需要知道从哪一边进行操作。为了方便，我们直接在数组 b b b上进行减操作。
如果我们从左边开始，进行了一些操作后， b b b数组是 [ 0 , 2 , . . . ] [0,2,...] [0,2,...],那么我们就无法判断，最优情况是从第一位开始减，还是从第二位开始减去。

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

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

我们在第 n ( n ≥ k ) n(n ge k) n(n≥k)上减去 k k k,那么前面需要减去的数就会递减。我们令 s u m sum sum是当前需要减去的数。

那么初始状态下, s u m = k sum = k sum=k,然后前面的数就需要依次是 s u m − = 1 , s u m − = 1 , s u m − = 1... sum-=1,sum-=1,sum-=1... sum−=1,sum−=1,sum−=1...，我们用 c n t cnt cnt表示这个减去的值,只进行了依次减去操作的话，那么 c n t = 1 cnt=1 cnt=1

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

那么我们考虑在减去的过程中，在 p p p位置减一个数:
假设我们需要减去 x ∗ k x * k x∗k(即进行了 x x x次减去操作),那么 s u m + = x ∗ k , c n t + = x sum+=x * k,cnt += x sum+=x∗k,cnt+=x,那么在 p − k p - k p−k位置之后，就不要再考虑这个减去操作了，所以 c l [ p − k ] + = x cl[p-k] += x cl[p−k]+=x

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

#include 
#include 
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("%lldn", ans);
    return 0;
}