371. Wine Trading in Gergovia

n villages sit along a straight road, numbered 1 to n from west to east. Village i's wine balance is a[i]: positive means a surplus of that many units to sell, negative means a need of that many units to buy (balances always sum to 0). Wine can only move between adjacent villages, and moving one unit across one village-to-village segment costs 1 unit of work. Find the minimum total work needed to satisfy every village. (Classic SPOJ 'GERGOVIA' problem.)

Input: The first line contains an integer n, the number of villages. The second line contains n space-separated integers, each village's wine balance (positive for surplus, negative for need). Output: Print a single integer - the minimum total work needed to satisfy every village.

2 <= n <= 10^5, -1000 <= a[i] <= 1000, sum of a[i] = 0

No sorting, graph traversal, or explicit simulation of wine movement is needed at all - the entire problem reduces to a single linear scan with a running sum, once you see the prefix-sum connection.

Villages along a road have wine surpluses or deficits; find the minimum total work to balance everyone, moving wine only between adjacent villages. Brute force: Simulate actual wine transfers between adjacent villages step by step, tracking exactly how much moves across each segment through some routing strategy - this works but is unnecessarily complex compared to recognizing a direct mathematical shortcut. Optimised: The KEY insight is that the amount of wine that MUST cross any given road segment is exactly the running total of everything imbalanced so far on one side of it - this is captured directly by the PREFIX SUM at that point, and since moving wine across a segment costs 1 unit of work PER UNIT moved, summing the absolute prefix sums across every segment gives the total work with no simulation needed at all.

Repeatedly rescan the whole village array to find a village with leftover surplus and the nearest village with leftover deficit, physically transfer wine unit by unit (or in bulk) between them across the intervening distance, add the distance-weighted cost, and update both villages' remaining balances. Keep repeating this full rescan-and-transfer cycle until every village's balance reaches zero. Because each transfer requires rescanning large portions of the array and the number of transfer rounds can itself be large, this is far slower than necessary, though it mirrors literally moving physical units of wine along the road. Time: O(n^2) or worse Space: O(n)

Scan the villages left to right while maintaining a running prefix sum of the balances seen so far. At the boundary between village i and village i+1, exactly |prefix sum up to i| units of wine must cross that single segment (whatever imbalance exists to the left must be resolved by flowing across that one point), and this is added directly to the total cost regardless of how the transfers are eventually paired up. Summing the absolute prefix sum at every one of the n-1 boundaries in one pass gives the minimum total work with no explicit pairing or matching logic at all. Time: O(n) Space: O(1) extra

Walk two pointers i and j across the village array: i finds the next village with remaining surplus, j finds the next village with remaining need. Match min(surplus at i, need at j) units between them, paying cost equal to that amount times the distance |i - j|, then reduce whichever side got fully satisfied and advance that pointer, repeating until both pointers reach the end. Each village is only ever advanced past once, so the whole process runs in a single linear pass while directly modeling the transfer between matched village pairs. Time: O(n) Space: O(1) extra

1. Track the RUNNING PREFIX SUM of balances as you sweep from west to east - this running sum represents exactly how much wine must cross the road right after that specific point. 2. The total work is simply the SUM of the ABSOLUTE VALUE of this running prefix sum, taken after every single village. 3. A single linear pass over the array computes this directly - no sorting or explicit routing simulation needed.

Time: O(n) - one single linear pass computing and summing running prefix sums. Space: O(1) extra space - just a running sum and a running total.

a village with balance 0, balances alternating in sign along the road, and n at its maximum of 10^5 with balances up to +-1000 to confirm the prefix-sum approach runs efficiently.

Be ready to explain WHY the prefix sum at each point represents exactly the wine crossing that segment - this elegant reduction from a seemingly complex routing/logistics problem to a simple prefix-sum computation is the entire crux of the problem, and is a great example of finding hidden mathematical structure.