Balancing Bacteria题解

jokiii · 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;
}