自动搬运

查看原文

来自洛谷，原作者为

	jokiii ·

搬运于2025-08-24 22:55:01，当前版本为作者最后更新于2024-01-27 21:41:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：第一眼看到题在一个给定序列上加上一个等差数列就觉的和这题有点类似，但发现首项和公差均为 $1$ 且结束点一定为 $n$ 便发现了有蹊跷。

• 题意：给定数组 $a$，可以在任意位置 $i$ 加上（或减去）一个首项为 $1$，公差为 $1$，长度为 $n-i+1$（即结束点为 $n$）的等差数列。问需要加（或减）几个等差数列可使 $a$ 中的值全为 $0$。

此题正解应为：二阶差分。

观察到

可得结论：在差分两次后的数组的 $i$ 位置上加 $1$，就等价于在原数组 $i$ 至 $n$ 上加上了一个首项为 $1$ 公差为 $1$ 的等差数列。

所以，数组 $a$ 两次差分后所有数的绝对值的和，即为将原数列应加上等差数列的个数。

代码如下

#include <iostream>
#include <cmath>
using namespace std;
long long n,a[200010],s[200010],s2[200010],ans;
//别忘了long long
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        s[i]=a[i]-a[i-1];
        s2[i]=s[i]-s[i-1];
        ans+=abs(s2[i]);
    }
    cout<<ans;
}