题解 guP4552 IncDec Sequence

这道题是一道差分的题目

差分数组p即p[i]=a[i]-a[i-1]

如果我们把一个区间[l,r]里的数+1，那么我们不难发现p[l]'=a[l]+1-a[l-1]=p[l]+1,p[r+1]'=a[r+1]-(a[r]+1)=p[r+1]-1

即一次将两个p[i]+1 or -1

还有一种情况可以使p[l]+1 or -1

---------------差分数组介绍完毕-------------------------

首先我们看第一小问：输出最少操作次数使所有数相等，即令p[i]==0(i!=1)

我们可以根据之前得到的结论推广：

若 p[2]1,p[3]-2，那么我们最少需要两次操作；

若 p[2]1,p[3]-2,p[4]==4，那么我们最少需要五次操作；

若 p[2]1,p[3]-2,p[4]4,p[5]-2，那么我们最少需要五次操作；

......

不难看出，若把原p数组中正数之和表示为a，负数绝对值之和表示为b，那么我们最少需要max(a,b)次操作。

再看第二小题。

题目可以理解为：在一问的条件下，p[1]的值有多少种情况？

无需赘述，我们可以发现，当我们min(a,b)次操作后，数组p中定然只会剩下p[1]与一些同号的数。对于之后的|a-b|次操作，我们可以选择让p[1]变动或不变，这样一来p[1]的值就会有1+max(a,b)种可能的值。

完结撒花qwq~

代码：

#include<bits/stdc++.h>

using namespace std;

long long n,a[101000],p[101000],z,f,ans;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

    {

        scanf("%lld",&a[i]);

        p[i]=a[i]-a[i-1];

    }

    for(int i=2;i<=n;i++)

    {

        if(p[i]>0)

        z+=p[i];

        else

        f-=p[i];

    }

    long long ans=abs(z-f),an=max(z,f);

    cout<<an<<"\n"<<1+ans;

    return 0;

}

巴特西

题解 guP4552 IncDec Sequence

这道题是一道差分的题目

---------------差分数组介绍完毕-------------------------

最新文章

热门文章