Show problems as
Classic problem #2448HardArrayBinary SearchGreedySortingPrefix Sum

Minimum Cost to Make Array Equal

Real-world version: Regrading the Survey Pegs
Tracked in this browser only
Read Minimum Cost to Make Array Equal on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey crew has driven a row of pegs into a slope. Peg i currently sits at height height[i] centimetres, and moving that peg one centimetre costs effort[i] units of work whether it goes up or down.

The crew now has to bring every peg to one shared height. They may pick any whole number of centimetres as that shared height, and each peg may be moved by any whole number of centimetres.

Return the least total work that levels all the pegs.

Examples

Example 1

Input
height = [12, 9, 20, 9], effort = [5, 2, 1, 3]
Output
23

Levelling everything to height 12 moves the first peg not at all, both pegs at height 9 up by 3 and the peg at height 20 down by 8, for `2*3 + 3*3 + 1*8 = 23` units of work.

Example 2

Input
height = [4, 7, 11, 16, 21], effort = [1, 1, 1, 1, 40]
Output
46

Levelling everything to height 21 leaves the last peg alone and raises the other four by 17, 14, 10 and 5 centimetres at one unit of work per centimetre, for 46 units in total.

Example 3

Input
height = [6, 6, 6], effort = [9, 2, 5]
Output
0

The pegs already share a height, so nothing has to move.

Constraints

  • 1 <= height.length <= 10^5
  • height.length == effort.length
  • 1 <= height[i], effort[i] <= 10^6
  • The pegs are laid out so that the answer is at most 10^15.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def least_regrade_work(height: list[int], effort: list[int]) -> int:
Java
public long leastRegradeWork(int[] height, int[] effort)

More on the same topics