P4552 [Poetize6] IncDec Sequence - 洛谷

差分+貪心

根據題目：一段區間都加1或減1 ， 可以想到差分

構建差分數組：sub? ?我們要讓除了sub[1] , 其他全是0

我們可以的操作是：l+1 , r-1? ? or? ?l-1 , r+1? ?or? ? 一個數+1 / -1

所以找到 一對正負數 就可以消掉? ?小的那個數

消掉剩下消不掉的 ， 就自己單獨消掉

所以 最少操作 ： max(? sum_p , sum_n? )

種類數：此時diff = abs(sum_p -? sum_n )? ?剩下不可用一對正負數消掉的，需要自己消掉的數

if? diff < 0? ? ,? 可以給sub[1] 減去（1 - diff)? 還要+上原來的sub[1]

if? diff >?0? ? ,? 可以給sub[1] 加（1 - diff)? 還要+上原來的sub[1]

sub[1]是多少整個數組最后就是多少 ， 所以有 diff +1 種

#include <bits/stdc++.h>
using namespace std;
#define int long longsigned main() {int n;cin >> n;vector<int> a(n+1,0);vector<int> sub(n+1,0);for(int i=1;i<=n;i++){cin>>a[i];    sub[i] = a[i] - a[i-1];}int sum_p = 0 , sum_n = 0;for(int i=2;i<=n;i++){if(sub[i] >= 0){sum_p += sub[i];}else{sum_n += sub[i];}}sum_n = -sum_n;cout<<max(sum_p , sum_n)<<endl;cout<<abs(sum_p - sum_n)+1<<endl;return 0;
}