#PU1373. USACO 2024 January Contest, Bronze — Problem 3. Balancing Bacteria

    ID: 1544 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:jan24来源:usaco.orgscoring:equal_test_cases二分答案线段树

USACO 2024 January Contest, Bronze — Problem 3. Balancing Bacteria

USACO 2024 January Contest, Bronze — Problem 3. Balancing Bacteria

题目描述

Farmer John has NN (1≤N≤2⋅1051\le N\le 2\cdot 10^5) patches of grass in a line, where patch ii has a level of bacteria that differs by aia_i from that of healthy grass (−1015≤ai≤1015-10^{15}\le a_i \le 10^{15}). For example, if ai=−3a_i = -3, then patch ii has a level of bacteria 3 lower than normal, and would need exactly 3 additional units of bacteria added to raise it to the point where it is considered healthy. Farmer John wants to ensure every patch of grass is corrected to have a healthy level of bacteria. Conveniently, he owns two brands of pesticide that he can spray on his field, one that adds bacteria and one that removes bacteria. When Farmer John sprays either type of pesticide, he stands in patch NN (the rightmost patch) and selects a power level LL for his sprayer (1≤L≤N1 \leq L \leq N). The sprayer has the most impact on patches near Farmer John, with diminishing effect farther away. If Farmer John chooses the pesticide that adds bacteria, then LL units of bacteria will be added to patch NN, L−1L-1 units to patch N−1N-1, L−2L-2 units to patch N−2N-2, and so on. Patches 1…N−L1 \ldots N-L will receive no bacteria, since the sprayer isn't set to a level powerful enough to reach them. Similarly, if Farmer John chooses the pesticide that removes bacteria, then LL units of bacteria will be removed from patch NN, L−1L-1 units will be removed from patch N−1N-1, and so on. Again, patches 1…N−L1 \ldots N-L will be unaffected. Find the minimum number of times Farmer John has to apply his sprayer such that every patch of grass has the recommended value of bacteria for healthy grass. It is guaranteed that the answer is at most 10910^9.

输入格式

The first line contains NN. The second line contains NN integers a1…aNa_1\dots a_N, the initial bacteria levels of each patch of grass.

输出格式

The minimum number of applications necessary to make every patch of grass have the recommended value of bacteria for healthy grass.

数据范围

Inputs 3-5: N≤103N \le 10^3, the answer is at most 10310^3 Inputs 6-10: N≤103N \le 10^3 Inputs 11-15: No additional constraints. Problem credits: Rohin Garg

样例

样例 1

2
-1 3
6
Use the type of pesticide that removes bacteria, at a power level of 1, five
times. Then use the type of pesticide that adds bacteria, with a power level of
$2$, one time.

样例 2

5
1 3 -2 -7 5
26

提示

use of 64-bit integer data types (e.g., a "long long" in C/C++).