题解 | #积木大赛# && 道路铺设

链接：https://ac.nowcoder.com/acm/contest/19483/I
简要题意：对于一个全0数组，每次可以选一段[l,r]，将里头元素全部+1.问要想生成给定数组a，至少需要几次操作
分析：差分数组的应用
考虑差分数组。每次选择长度[l,r]进行+1时，差分数组中d[r+1]-1，d[l]+1.因此，差分数组中的正数和与负数和相等，且恰好等于操作次数
需要注意全0数组的条件，读入a[1]到a[n]之后，记得考虑a[0]=0和a[n+1]=0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))

int a[100010];
int d[100010];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    ll ans=0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        d[i]=a[i]-a[i-1];
        if(d[i]>0)    ans+=d[i];
    }
    a[n+1]=0;
    d[n+1]=a[n+1]-a[n];
    if(d[n+1]>0)    ans+=d[n+1];
    cout << ans;
    return 0; 
}

道路铺设https://ac.nowcoder.com/acm/contest/19483/J
每次选一段[l,r]的区间，将里头数字-1，问减几次后能变成全0
道理同上，考虑差分数组中正数的总和