P10663: 平衡的细菌

---

【题目描述】

【题目描述】 Farmer John 有N（1≤N≤2⋅10⁵）块草地排成一行，其中草地i的细菌水平与健康草的细菌水平相差ai（−10¹⁵≤ai≤10¹⁵）。例如，如果ai=−3，则草地i的细菌水平比正常水平低 3，需要额外添加3 个单位的细菌才能将其提高到被认为是健康的程度。 Farmer John 想要确保每一块草地都被修复至健康的细菌水平。方便的是，他有两种品牌的农药可以喷洒在他的田地里，一种可以添加细菌，另一种可以去除细菌。当 Farmer John 喷洒任一类型的农药时，他站在草地N（最右边的草地）并为他的喷雾器选择功率等级L（1≤L≤N）。 喷雾器对靠近 Farmer John 的草地效果最大，随着距离增加效果逐渐减弱。如果 Farmer John 选择添加细菌的农药，则L单位的细菌将被添加至草地N，L−1单位添加至草地 N−1，L−2单位添加至草地N−2，以此类推。草地1…N−L不会得到任何细菌，因为喷雾器设置的功率不足以到达它们。类似地，如果 Farmer John 选择去除细菌的农药，则L单位的细菌将被从草地N去除，L−1单位被从草地 N−1去除，以此类推。同样，草地 1…N−L将不受影响。 求 Farmer John 使用喷雾器的最少次数，使得每块草地都具有健康草的推荐细菌值。输入保证答案不超过 10⁹。 注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。 【输入格式】 输入的第一行包含N。 第二行包含N个整数a1…aN，为每块草地的初始细菌水平。 【输出格式】 输出一个整数，为使每块草地都具有健康草的推荐的细菌值所需使用喷雾器的最少次数。 【输入样例一】 2 -1 3 【输出样例一】 6 【样例说明一】 使用去除细菌的农药，功率等级为 1，使用五次。然后使用添加细菌的农药，功率等级为2，使用一次。 【输入样例二】 5 1 3 -2 -7 5 【输出样例二】 26 【数据约束】 测试点 3-5：N≤10³，答案不超过10³。 测试点 6-10：N≤10³。 测试点 11-15：没有额外限制。  

【输入】

输入的第一行包含N。

第二行包含N个整数a1…aN，为每块草地的初始细菌水平。

【输出】

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

题目类型~

竞赛题 

咻咻~

提交答案 状态 返回