leetcode

0 class Solution {

1 public:

2 long long minCost(const vector<int> &nums, const vector<int> &cost) {

3 const auto calc = [&const](int target) {

4 long long res = 0;

5 for (int i = 0; i < nums.size(); i++)

6 res += (long long)abs(nums[i] - target) * cost[i];

7 return res;

8 };

9

10 long left = 1L, right = 1000000L;

11 for (long num : nums) {

12 left = min(left, num);

13 right = max(right, num);

14 }

15

16 long ans = calc(1);

17 while (left < right) {

18 long mid = (left + right) / 2;

19 long y1 = calc(mid), y2 = calc(mid + 1);

20 ans = min(y1, y2);

21 if (y1 < y2)

22 right = mid;

23 else

24 left = mid + 1;

25 }

26 return ans;

27 }

28 };