1110. Weighted Jobs, Shortest First

One machine runs n jobs back to back with no idling, in an order you choose. Job i takes p units of work and carries an IMPORTANCE w. If a job finishes at time C, it costs w * C.

Print the smallest possible total cost.

jobs (p=3,w=1) (p=1,w=2) (p=2,w=3) -> 17 jobs (p=5,w=7) -> 35 jobs (p=2,w=2) (p=4,w=4) (p=6,w=6) -> 100

Trace the first line. The ratios p / w are 3, 0.5 and 0.667, so the order is (1,2), (2,3), (3,1). They finish at 1, 3 and 6, costing 2*1 + 3*3 + 1*6 = 17.

## What most people try first

Shortest first, which is exactly right when every importance is 1 and is problem #1102. Here is the input that kills it, and it is in the tests:

jobs (p=1,w=1) (p=2,w=10) shortest first: order (1,1) (2,10), finishing at 1 and 3, costing 1 + 30 = 31 ratio order: order (2,10) (1,1), finishing at 2 and 3, costing 20 + 3 = 23

Most-important first is the mirror mistake, right when every length is 1 and wrong as soon as a very important job is also very long.

Both are special cases of the rule below, and both are wrong in general: the machine spends TIME and earns against IMPORTANCE, so what matters is how much time a job costs per unit of importance it clears.

Trying every order costs n!.

## The method

Sort by the ratio p / w ASCENDING, computed without division, then sweep.

sort with the comparator: a before b when p_a * w_b < p_b * w_a clock = 0 total = 0 for (p, w) in that order: clock = clock + p total = total + w * clock

One sort and one pass.

## Why the ratio, argued by an adjacent swap

Take any order and look at two ADJACENT jobs, a immediately before b, starting at time S. Everything outside the pair is untouched by a swap, because the pair occupies S to S + p_a + p_b either way.

Before the swap the pair costs w_a (S + p_a) + w_b (S + p_a + p_b). After the swap it costs w_b (S + p_b) + w_a (S + p_a + p_b).

Subtract. The S terms cancel, w_a p_a and w_b p_b cancel, and what is left is

before - after = w_b * p_a - w_a * p_b

So the swap helps exactly when w_b p_a > w_a p_b, that is when p_a / w_a > p_b / w_b. An order is therefore unimprovable by adjacent swaps exactly when it is sorted by p / w ascending, and since adjacent swaps can turn any order into any other, that order is optimal.

## Why the comparator is a total order

Compare a and b by p_a * w_b against p_b * w_a rather than by dividing. That is the same relation as p_a / w_a < p_b / w_b because every w is at least 1 and so strictly positive, and multiplying an inequality by a positive number is reversible.

Transitivity follows from the division form: x < y and y < z for real numbers gives x < z. Since the cross-multiplied form is equivalent to the division form for positive weights, it is transitive too, and it is total. Without the positivity of w the cross-multiplication would flip and the relation would not be an order at all, which is why the constraints say w >= 1.

Use the cross-multiplied form in code anyway: floating-point division of two integers up to 10^4 is exact enough here, but the integer form is exact everywhere and costs nothing.

## The boundary that breaks a careless implementation

Ties. When p_a * w_b == p_b * w_a the two jobs may be run in either order for exactly the same cost, so the comparator must report "equal" rather than claiming an order. A comparator that returns true for both (a, b) and (b, a) is not a strict weak ordering and in C++ that is undefined behaviour.

## Sizes

n reaches 10^5, and p and w each reach 10^4. The clock reaches 10^9, and the total reaches about 10^9 * 10^9 = 10^18, which fits in a signed 64-bit integer but is enormously past the 2147483647 limit of a 32-bit one. Seven jobs with p = w = 10^4 already cost 2.8 * 10^9, which is the eighth test. The comparator's products reach 10^8, which does fit in 32 bits.

## A related problem

Problem #1102 is this problem with every importance equal to 1, where p / w collapses to p and the rule becomes plain shortest-first. Reading the two proofs side by side shows that the same adjacent swap produced both, with the ratio appearing exactly where the weights do.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ p ≤ 10000` - `1 ≤ w ≤ 10000`