璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:luogup10133
problems
名称Balancing Bacteria B
题目编号USACO24JAN B3
题目链接luogu.com.cn/…
来源USACO
算法分类差分
难易程度一般般

Balancing Bacteria B

想法

题目大意:给数组增加公差为1的等差数列。

等差数列 1 2 3 4 5
差分 1 1 1 1 1
二阶差分 1 0 0 0 0

可以发现,每次二阶差分增加1,整体增加一个等差数列,而想让数据全为0,故二维差分也全为0,所以需要增加与二阶差分相反的等差数列。

代码实现

#include<cstdio>
#include<algorithm>
using namespace std;
 
const int N = 1e5*2+10;
int line[N], d[N], D[N];
 
int main() {
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &line[i]);
    int cnt = 0;
    for(int i=1; i<=n; i++) {
        d[i] = line[i] - line[i-1];
        D[i] = d[i] - d[i-1];
        cnt += abs(D[i]);
    }
    printf("%d", cnt);
    return 0;
}
/app/www/public/data/pages/icpc/problems/luogup10133.txt · 最后更改: 2024/03/27 01:58 由 温婕莺