AcWing 100. 增减序列
原题链接
中等
思路:差分
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
using namespace std;
#define endl "\n"
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define fir first
#define sec second
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
const int N = 100010;
int n, a[N], d[N];
int main(){
ios;
cin >> n;
rep(i, 1, n){
cin >> a[i];
}
d[1] = a[1];
rep(i, 2, n){
d[i] = a[i] - a[i - 1];
}
ll sum0 = 0, sum1 = 0;
rep(i, 2, n){
if (d[i] > 0){
sum0 += d[i];
}
else{
sum1 -= d[i];
}
}
ll opt = min(sum1, sum0) + abs(sum1 - sum0);
ll ans = abs(sum1 - sum0) + 1;
cout << opt << endl << ans << endl;
return 0;
}