[cf] 802 div2 C. Helping the Nature

前言

t a g : tag : tag:差分 传送门:

题意 : 给定多个树木的水分值 − 1 0 9 ≤ a i ≤ 1 0 9 - 10^9 \le a_i \le 10^9 −109≤ai​≤109

你可以进行如下三个操作 :

1. 将 1... i 1...i 1...i的树木的水分 − 1 -1 −1
2. 将 i , i + 1.... n i,i+1....n i,i+1....n的树木的水分 − 1 -1 −1
3. 将所有树木的水分 + 1 +1 +1

询问 最小的操作次数 使得最后所有树木的水分 = 0 =0 =0

思路:

第一种操作对应差分的 : d [ 1 ] − 1 , d [ i + 1 ] + 1 d[1]-1,d[i+1]+1 d[1]−1,d[i+1]+1

第二种操作对应 : d [ i ] − 1 , d [ n + 1 ] + 1 d[i]-1,d[n+1]+1 d[i]−1,d[n+1]+1

第三种操作对应 d [ 1 ] + 1 , d [ n + 1 ] − 1 d[1]+1,d[n+1]-1 d[1]+1,d[n+1]−1

code :

ll n,a[N],d[N];
void solve(){
	cin>>n;
	for(int i=1;i>a[i];
		d[i] = a[i] - a[i-1];
	}
	
	
	ll res = 0 ;
	
	for(int i=n;i>=2; i -- ){
	
		if(d[i] >= 0 ) res += d[i];
		else{
			res -= d[i];
			d[1] += d[i];
		}
	}
	
	
	cout