Common Setting at Different Step Prices

Hard

There are n dials, and dial i is set to values[i]. In one step you can turn any dial up or down by 1; a step of dial i costs prices[i]. All dials must be set to the same value. Return the minimum total cost.

Example 1

values=[4, 10, 7], prices=[1, 1, 5] → 6

Moving the expensive third dial does not pay off, so set everything to 7: raise the first by 3 (cost 3) and lower the second by 3 (cost 3), 6 in total.

Example 2

values=[5, 5], prices=[2, 9] → 0

The values already match.

Example 3

values=[1, 8, 3, 6], prices=[3, 2, 2, 4] → 25

Constraints

1 ≤ n ≤ 10⁵
n = len(values) = len(prices)
1 ≤ values[i], prices[i] ≤ 10⁶
The answer does not exceed 2⁵³ − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Binary Search Prefix Sum Sorting

Similar problems

Flowerbed Beauty on a Budget Hard Even Out With Increments Medium Rug Over Painted Stretches Medium Most Items Within Budget Easy Richest Row of Houses Medium

Input

values=[4, 10, 7], prices=[1, 1, 5]

Expected

Run checks the first 3 tests in your browser. Submit checks all 112 tests on the server, hidden ones included.