Restore the Forest’s Moisture
Autumn Tournament (2023)
Submission name: nature.cpp
Problem summary
Make every array value zero. An operation subtracts1 from a prefix, subtracts1 from a suffix, or adds1 to the entire array. Find the minimum number of operations. Values may initially be negative.
Input
n, followed by n signed moisture values.
Output
The minimum number of operations.
Constraints
1 ≤ n ≤ 200000; −10^9 ≤ ai ≤ 10^9.
Worked example
Original statement sample.
Input
3 10 4 7
Output
13
Solution analysis
- Adjacent differences isolate the effects of operations. An upward jump ai−ai−1>0 requires that many suffix decrements starting at i. A downward jump requires that many prefix decrements ending at i−1. Let up and down be the sums of these positive jumps in each direction.
- Performing exactly these necessary decrements makes the array constant. Its value is a1−down: every required prefix decrement affects the first element, while required suffix decrements do not. Clear the constant with |a1−down| whole-array operations, using a decrement when positive and an increment when negative.
- For [10,4,7], down=6 and up=3. Required operations flatten the array to4, which needs four more decrements. The answer is6+3+4=13. For [−2,−2,−2], there are no jumps and two increments suffice.
Why it works
Each positive adjacent difference needs its stated suffix decrements and each negative difference needs its stated prefix decrements; using extra opposing operations at a boundary costs two operations and can alter the remaining constant by only one, so it cannot improve the total. After the mandatory boundary corrections, whole-array operations optimally clear the residual constant. The construction attains this lower bound.
Watch out. Do not assume values are nonnegative. Differences can be2·10^9 and their total can be about2·10^14, so accumulate in long long. A whole-array decrement is a permitted prefix or suffix decrement.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cstdlib>
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
long long first;
cin>>first;
long long previous=first;
long long up=0;
long long down=0;
for(int i=1;i<n;i++){
long long current;
cin>>current;
if(current>previous){
up+=current-previous;
}
else{
down+=previous-current;
}
previous=current;
}
// Boundary corrections leave every element equal to first-down.
cout<<up+down+llabs(first-down)<<'\n';
}