2448.使数组相等的最小开销

链接：2448.使数组相等的最小开销
难度：Hard
标签：贪心、数组、二分查找、前缀和、排序
简介：请你返回使 nums 中所有元素 相等 的 最少 总开销。

题解 1 - cpp

• 编辑时间：2022-10-23
• 执行用时：180ms
• 内存消耗：82.3MB
• 编程语言：cpp
• 解法介绍：贪心，最后化为的值一定是 nums 中存在的值，通过按值的大小排序后，结果成凹型，找到最低点即结果。

struct Node {
    int num, cost;
    Node(int num, int cost): num(num), cost(cost) {}
    long long getCost(int num) {
        return abs(static_cast<long long>(num) - this->num) * cost;
    }
};
class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        int n = nums.size();
        vector<Node> list;
        for (int i = 0; i < n; i++) list.push_back(Node(nums[i], cost[i]));
        sort(list.begin(), list.end(), [](Node &a, Node &b){ return a.num < b.num; });
        int l = 0, r = n - 1;
        long long ans = 0;
        while (l < r) {
            int m1 = (l + r) / 2, m2 = m1 + 1;
            long long m1cost = comp(list, list[m1].num), m2cost = comp(list, list[m2].num);
            if (m1cost >= m2cost) l = m2, ans = m2cost;
            else r = m1, ans = m1cost;
        }
        return ans;
    }
    long long comp(vector<Node> &list, int num) {
        long long ans = 0;
        for (int i = 0; i < list.size(); i++) {
            ans += list[i].getCost(num);
        }
        return ans;
    }
};