题解 | #积木大赛# && 道路铺设
链接：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
道理同上，考虑差分数组中正数的总和
