洛谷 P5019 铺设道路（差分）

嗯...

 

题目链接：https://www.luogu.org/problem/P5019

 

首先简化一下题意：

给定一个长为N的数组，每次操作可以选择一个区间减去1，问最少多少次操作可以将数组中的数全变成0 N≤100000

思路：

首先对于第一个数字d_1我们至少需要在上面花d_i次，然后考虑每一个d_i，对于它比上一个数字小（或等于）的那一部分，

我们可以在对上一个数字操作时一块操作。如果d_i > d_i - 1，也就是说它比上一个数大，那么我们就必须多进行d_i - d_i - 1次操作。

很明显，数与数之间会有差，而差会造成一些区间问题，所以这道题的正解是差分...

我们用b数组维护差分，然后将大于0的差分数组加到ans中即可。

AC代码：

#include<cstdio>
#include<iostream>

using namespace std;

int ans, d[100005], b;

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &d[i]);
        b = d[i] - d[i - 1];
        if(b > 0) ans += b;
    }
    printf("%d", ans);
    return 0;
}