链接: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
道理同上,考虑差分数组中正数的总和