Link to the problem: [click here](https://oj.uz/problem/view/LMIO19_bulves)↵
↵
**Summary.** Given two arrays $a$ and $b$ of length $n$. In one operation, we can move one unit from $a_i$ to an adjacent position. We need to find the minimum number of operations such that $a_i \geq b_i$ for all $i$. It is guaranteed that a solution always exists.↵
↵
**Constraints.** $n \leq 5\cdot 10^5; a_i, b_i \leq 10^6$.↵
↵
I have already come up a approach for the subtasks with $\sum_{i = 1}^n a_i = \sum_{i = 1}^n b_i$, when the target become to make $a_i = b_i$ for all $i$.↵
↵
Let $pref_i = \sum_{i = 1}^n (a_i - b_i)$. If $pref_i > 0$, it means that the left side has $pref_i$ extra units, so we have to move them to the right side. Otherwise, the left side is missing of units, so we have to move $-pref_i$ units from the right side to the left side. In both cases, exactly $|pref_i|$ units will cross the gap between positions $i$ and $i + 1$. This implies that the answer will be $\sum_{i = 1}^n |pref_i|$.↵
↵
However, I am stuck on how to generalize this to the full problem and also could not understand the accepted submissions. Any hints or explanations would be appreciated. Thanks!
↵
**Summary.** Given two arrays $a$ and $b$ of length $n$. In one operation, we can move one unit from $a_i$ to an adjacent position. We need to find the minimum number of operations such that $a_i \geq b_i$ for all $i$. It is guaranteed that a solution always exists.↵
↵
**Constraints.** $n \leq 5\cdot 10^5; a_i, b_i \leq 10^6$.↵
↵
I have already come up a approach for the subtasks with $\sum_{i = 1}^n a_i = \sum_{i = 1}^n b_i$, when the target become to make $a_i = b_i$ for all $i$.↵
↵
Let $pref_i = \sum_{i = 1}^n (a_i - b_i)$. If $pref_i > 0$, it means that the left side has $pref_i$ extra units, so we have to move them to the right side. Otherwise, the left side is missing of units, so we have to move $-pref_i$ units from the right side to the left side. In both cases, exactly $|pref_i|$ units will cross the gap between positions $i$ and $i + 1$. This implies that the answer will be $\sum_{i = 1}^n |pref_i|$.↵
↵
However, I am stuck on how to generalize this to the full problem and also could not understand the accepted submissions. Any hints or explanations would be appreciated. Thanks!
