2448. 使数组相等的最小开销
给你两个下标从 0 开始的数组 nums 和 cost ,分别包含 n 个 正 整数。
你可以执行下面操作 任意 次:
将 nums 中 任意 元素增加或者减小 1 。
对第 i 个元素执行一次操作的开销是 cost[i] 。
请你返回使 nums 中所有元素 相等 的 最少 总开销
示例 1:
输入:nums = [1,3,5,2], cost = [2,3,1,14]
输出:8
解释:我们可以执行以下操作使所有元素变为 2 :
- 增加第 0 个元素 1 次,开销为 2 。
- 减小第 1 个元素 1 次,开销为 3 。
- 减小第 2 个元素 3 次,开销为 1 + 1 + 1 = 3 。
总开销为 2 + 3 + 3 = 8 。
这是最小开销
法1:类比货仓选址问题贪心
long long minCost(vector<int>& nums, vector<int>& cost) {
int n = nums.size();
vector<PII> a;
long long sum = 0;
for(int i = 0; i < n; i ++){
a.push_back({nums[i], cost[i]});
sum += cost[i];
}
sort(a.begin(), a.end());
sum /= 2;
long long s = 0;
int mid = 0;
for(int i = 0; i < n; i ++) {
s += a[i].second;
if(s >= sum){
mid = i;
break;
}
}
long long ans = 0;
for(int i = 0; i < n; i ++){
ans += (long long)abs(a[i].first - a[mid].first) * a[i].second;
}
return ans;
};
法2:数学推导
枚举某点 然后分别计算前半部分消耗的代价和后半部分消耗的单价
class Solution {
public:
long long minCost(vector<int>& nums, vector<int>& cost) {
int n = nums.size();
vector<long long> s(n + 1), add(n + 1);
vector<pair<int, int>> a;
for(int i = 0; i < n; i ++){
a.push_back({nums[i], cost[i]});
}
sort(a.begin(), a.end());
for(int i = 1; i <= n; i ++){
s[i] = s[i - 1] + a[i - 1].second;
add[i] = add[i - 1] + (long long)a[i - 1].first * a[i - 1].second;
}
long long ans = 1e18;
for(int i = 1; i <= n; i ++){
long long w = 0;
w += (long long)a[i - 1].first * s[i - 1] - add[i - 1];
w += (long long)add[n] - add[i] - a[i - 1].first * (s[n] - s[i]);
ans = min(ans, w);
}
return ans;
}
};