leetcode

commit 6a8d64dd6e703ff767604a84452f3a9327b4e209
parent 737e888f863b35e7e8384dcc7149ddca6c816b52
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 21 Jun 2023 18:10:48 +0200

Daily Problem

Diffstat:
A
Problems/2448.cpp
 | 
29
+++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/Problems/2448.cpp b/Problems/2448.cpp
@@ -0,0 +1,29 @@
+class Solution {
+public:
+  long long minCost(const vector<int> &nums, const vector<int> &cost) {
+    const auto calc = [&const](int target) {
+      long long res = 0;
+      for (int i = 0; i < nums.size(); i++)
+        res += (long long)abs(nums[i] - target) * cost[i];
+      return res;
+    };
+
+    long left = 1L, right = 1000000L;
+    for (long num : nums) {
+      left = min(left, num);
+      right = max(right, num);
+    }
+
+    long ans = calc(1);
+    while (left < right) {
+      long mid = (left + right) / 2;
+      long y1 = calc(mid), y2 = calc(mid + 1);
+      ans = min(y1, y2);
+      if (y1 < y2)
+        right = mid;
+      else
+        left = mid + 1;
+    }
+    return ans;
+  }
+};
diff --git a/README.md b/README.md
@@ -563,6 +563,7 @@ for solving problems.
 |  2421  |   Medium   | [Number of Good Paths](Problems/2421.cpp)                                                        |
 |  2439  |   Medium   | [Minimize Maximum of Array](Problems/2439.cpp)                                                   |
 |  2444  |    Hard    | [Count Subarrays With Fixed Bounds](Problems/2444.cpp)                                           |
+|  2448  |    Hard    | [Minimum Cost to Make Array Equal](Problems/2448.cpp)                                                               |
 |  2461  |   Medium   | [Maximum Sum of Distinct Subarrays With Length K](Problems/2461.cpp)                             |
 |  2465  |    Easy    | [Number of Distinct Averages](Problems/2465.cpp)                                                 |
 |  2466  |   Medium   | [Count Ways To Build Good Strings](Problems/2466.cpp)                                            |