823. Making Everything Equal When Moves Have Prices

A depot holds n items. Item i sits at position a[i], and moving it by one unit in either direction costs c[i]. Choose one target position and move every item to it. The target must be a whole number but may be any whole number, not only one that an item already occupies.

Print the smallest total cost.

positions 1 3 5 2 1, prices 2 3 1 14 4 -> 12 positions 2 2 2 2, prices 4 2 8 1 -> 0 positions 1 2 3, prices 100 1 1 -> 3

## The partner problem, and what changed

Problem 600 asks the same question with every price equal to 1, and its answer is to meet at the MEDIAN, which is found by sorting. That works because with equal prices the only thing that matters is how many items lie on each side of the target.

Prices break the counting argument, but not the structure. What matters now is not how many items are on each side, it is how much PRICE is on each side.

## The shape of the cost

Write f(t) for the total cost of meeting at t. Each item contributes c[i] * |a[i] - t|, which is a V shape, and a sum of V shapes is convex. Look at what happens when the target moves one step right:

f(t+1) - f(t) = sum of c[i] over items with a[i] <= t - sum of c[i] over items with a[i] > t

Every step right pays an extra c[i] for each item already passed and saves c[i] for each item still ahead. As t grows, items only ever move from the second group to the first, so this difference is NON-DECREASING. That is exactly the monotone predicate the search needs, and it is the derivative of the cost rather than the cost itself.

## The predicate

P(t): f(t) <= f(t+1)

P is false while stepping right still helps and true from the moment it stops helping, so the answers read no no no YES YES and the first YES is the cheapest target.

Searching f for its minimum directly does not work: f is not monotone, it falls and then rises. Searching the DIFFERENCE does work, because the difference is monotone. Recognising when to search a derivative rather than the value is the transferable idea here.

## The invariant and the bounds

lo = min(a), hi = max(a). The optimum is never outside that range: moving the target past the outermost item adds cost to every single item at once. The invariant is

> the smallest t with f(t) <= f(t+1) lies in [lo, hi].

On f(mid) <= f(mid+1) set hi = mid, keeping mid in play; otherwise lo = mid + 1.

## Why the loop terminates

mid = lo + (hi - lo) / 2 gives lo <= mid < hi, so mid + 1 is always a valid target inside the range and every branch shrinks hi - lo. Around 30 iterations for positions up to 10^9, each costing one pass over the items.

## What is printed when the predicate never fires

It always fires by t = hi, because at the largest position every item is at or below the target, so f(hi+1) - f(hi) is the sum of all the prices, which is positive. So there is always an answer, and the answer to a list that is already level is 0. That case is in the tests.

## Overflow

With n at 20000, prices at 100 and positions at 10^9, the total cost approaches 2 * 10^15. That fits in a signed 64-bit integer with room to spare and does not fit in 32 bits at all. In JavaScript it also stays inside the exact-integer range of a double, which ends just above 9 * 10^15.

## Cost

Time O(n log(max a)). Space O(n).

Constraints - `1 ≤ n ≤ 20000` - `1 ≤ a[i] ≤ 1000000000` - `1 ≤ c[i] ≤ 100`