P4552 [Poetize6] IncDec Sequence

题意：给出序列$a$，每次可以选择一个区间$[l,r]$，将区间内的数都$+1$或$-1$，问最少几次使序列中的数都相等 ------------ 先差分，得到相邻两数的差 那么每次操作就相当于在差分数组中进行修改 可以发现正数与负数可以相互抵消 最少操作次数就是正数和与负数和的绝对值的较大值 对于第二问，能产生贡献的就是不能抵消的那一部分 所以是两者差的绝对值$+1$ ``` #include<cstdio> #include<cctype> #include<cstdlib> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=1e5+5; int n; ll a[N],ans,res,t1,t2; inline ll read() { ll x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=0; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return w?x:-x; } int main() { n=read(); for (reg int i=1;i<=n;a[i++]=read()); for (reg int i=2;i<=n;i++) { ll x=a[i]-a[i-1]; if (x>0) t1+=x; else t2-=x; } printf("%lld\n%lld\n",max(t1,t2),abs(t1-t2)+1); return 0; } ```