P4552 [Poetize6] IncDec Sequence

2018-10-08 09:58:06


题意:给出序列 $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;
}