题解 P4552 【[Poetize6] IncDec Sequence】

Mr_QwQ · 2018-07-08 15:27:09 · 题解

这个题远没有NOI+吧……

毕竟我这种小蒟蒻都能做出来。

先差分一波，求出相邻两个数的差。

接下来的就成了：差分数组的一个数加1或减1（原数组里选上n或者选上1），或两个不同的数分别加1和减1，求把差分2-n变成0的最小步数。

于是乎我们发现：正数和负数可以对消

然后把能消掉的一步到位，不能两个一起消的就跟0（一个假想的位置，实际操作上选上1）或者n+1（选上n）消。

第一问完毕。

对于第二问，为了最小步数，显然只能靠最后不能跟别的一起消掉的数字贡献答案。那么如果跟1消就是改变了答案，跟n消就不改。

代码：

#include <iostream>
#include <cstdio>
using namespace std;
int n;
long long a[100010],x[100010],t1,t2;
long long myabs(long long t){
    if(t>0)return t;
    return -t;
}
long long mmax(long long x1,long long x2){
    if(x1>x2)return x1;
    return x2;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    for(int i=2;i<=n;i++){
        x[i]=a[i]-a[i-1];
        if(x[i]>0)t1+=x[i];
        else t2-=x[i]; 
    }
    printf("%lld\n%lld",mmax(t1,t2),myabs(t1-t2)+1);
    return 0;
}

你问我为什么WA了两次？因为我最开始写的是printf("%d\n%d"...)（逃