1108. Short Jobs First on k Machines

k counters serve n customers in parallel. Every customer is assigned to exactly one counter, each counter serves its customers one after another in an order you choose, and no counter ever idles. Customer i takes t[i] minutes.

A customer's WAITING time is how long passes before their own service starts, counting from time 0. Print the smallest possible total waiting time.

n = 5, k = 2, times 4 1 3 2 5 -> 7 n = 5, k = 1, times 4 1 3 2 5 -> 20 n = 5, k = 5, times 4 1 3 2 5 -> 0

Trace the first line. Put 1, 3, 5 on counter A and 2, 4 on counter B. Counter A's waits are 0, 1 and 4; counter B's are 0 and 2. The total is 7. No other split does better.

## What most people try first

Handing the next customer to the counter that is currently least busy, in the given order. That is a reasonable heuristic and it does not use the durations at all.

The second instinct is to sort ascending and DEAL the customers round-robin, one to each counter in turn. That is actually correct, and it is worth understanding why rather than trusting it, because the version that deals the LONGEST first is wrong.

Trying every assignment plus every order costs k^n times the orderings.

## The method

The whole answer collapses to a formula.

sort t ascending total = 0 for i from 0 to n-1: total = total + t[i] * ((n - 1 - i) / k) integer division

One sort and one pass.

## Where the formula comes from

Each customer's waiting time is the total of the durations of the customers served BEFORE them on their own counter. Turn that around: each customer's duration is added to the answer once for every customer served AFTER them on the same counter.

So the answer is sum over i of t[i] * (how many customers follow i on i's counter), and the question becomes: what multipliers are achievable?

With k counters, at most k customers can be last on their counter, so at most k can have multiplier 0. At most k more can have multiplier 1, and so on. The multipliers therefore form the multiset 0 repeated k times, 1 repeated k times, and so on, truncated at n values.

Given that fixed multiset, pairing the largest multiplier with the smallest duration minimises the total. That is the rearrangement inequality, and its proof is one more adjacent swap: if a larger duration carries a larger multiplier than a smaller duration, swapping the two multipliers changes the total by (bigger duration - smaller duration) * (smaller multiplier - bigger multiplier), which is negative, so the swap improves things.

Sorting ascending and assigning multiplier (n - 1 - i) / k does exactly that pairing.

## Checking the formula on the example

n = 5, k = 2, sorted 1 2 3 4 5. The multipliers are (4/2, 3/2, 2/2, 1/2, 0/2) = (2, 1, 1, 0, 0), so the total is 1*2 + 2*1 + 3*1 + 4*0 + 5*0 = 2 + 2 + 3 = 7, matching the hand-built schedule above.

With k = 1 the multipliers are 4 3 2 1 0, giving 4 + 6 + 6 + 4 + 0 = 20, which matches problem #1102's answer for the same data.

## The boundary that breaks a careless implementation

The division is integer division of n - 1 - i by k, and the index runs from 0. Using (n - i) / k gives every customer one multiplier too many and inflates the answer.

k >= n makes every multiplier 0 and the answer 0, which is worth testing because it is the case a loop over counters can get wrong.

## Sizes

n reaches 10^5, t reaches 10^9 and the worst multiplier is about n, so with k = 1 the answer reaches 5 * 10^18. That fits in a signed 64-bit integer, whose limit is about 9.2 * 10^18, and is enormously past the 2147483647 limit of a 32-bit one. The last test uses five customers of 10^9 on two counters for a total of 4 * 10^9.

## A related problem

Problem #1102 is this question with k fixed at 1, where the formula becomes a plain running sum. Going to k counters is what turns "how much has elapsed" into "how many people sit behind me on my own counter".

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ n` - `0 ≤ t[i] ≤ 1000000000` - the answer can reach about `5 * 10^18`, so it needs 64 bits