AcWing 5526. 平衡细菌

Week 3
3月4日

题目描述

农夫约翰有 $N$ 块草地排成一行，其中草地 $i$ 的细菌水平与健康草的细菌水平相差 $a_i$。

例如，如果 $a_i=-3$，则草地 $i$ 的细菌水平比正常水平低 $3$，需要额外添加恰好 $3$ 个单位的细菌才能将其提高到被认为是健康的程度。

农夫约翰想要确保每一块草地都被修复至健康的细菌水平。

方便的是，他有两种品牌的农药可以喷洒在他的田地里，一种可以添加细菌，另一种可以去除细菌。

当农夫约翰喷洒任一类型的农药时，他站在草地 $N$（最右边的草地）并为他的喷雾器选择功率等级 $L$（$1\le L\le N$）。

喷雾器对靠近农夫约翰的草地效果最大，随着距离增加效果逐渐减弱。

如果农夫约翰选择添加细菌的农药，则 $L$ 单位的细菌将被添加至草地 $N$，$L-1$ 单位添加至草地 $N-1$，$L-2$ 单位添加至草地 $N-2$，以此类推。

草地 $1\dots N-L$ 不会得到任何细菌，因为喷雾器设置的功率不足以到达它们。

类似地，如果农夫约翰选择去除细菌的农药，则 $L$ 单位的细菌将被从草地 $N$ 去除，$L-1$ 单位被从草地 $N-1$ 去除，以此类推。

同样，草地 $1\dots N-L$ 将不受影响。

求农夫约翰使用喷雾器的最少次数，使得每块草地都具有健康草的推荐细菌值。

输入保证答案不超过 $10^9$。

输入格式

输入的第一行包含 $N$。

第二行包含 $N$ 个整数 $a_1\dots a_N$，为每块草地的初始细菌水平。

输出格式

输出一个整数，为使每块草地都具有健康草的推荐的细菌值所需使用喷雾器的最少次数。

数据范围

$1\le N\le 2\times 10^5$,
$-10^{15}\le a_i\le 10^{15}$

输入样例1：

2
-1 3

输出样例1：

6

样例1解释

使用去除细菌的农药，功率等级为 $1$，使用五次。

然后使用添加细菌的农药，功率等级为 $2$，使用一次。

输入样例2：

5
1 3 -2 -7 5

输出样例2：

26

---

等差数列差分

---

AC_code

python">n = int(input())  
a = list(map(int, input().split()))  diff = [0] * n  
diff[0] = a[0]  
for i in range(1, n):  diff[i] = a[i] - a[i - 1]  diff2 = [0] * n  
diff2[0] = diff[0]  
for i in range(1, n):  diff2[i] = diff[i] - diff[i - 1]  ans = 0  
for i in range(n):  ans += abs(diff2[i])  
print(ans)

---

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注 谢谢