Leetcode 857 -- 贪心 | 数学

题目描述

雇佣 K 名工人的最低成本

思路

参考官方题解和这里。

代码1（正确）

class Solution {
public:double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {int n = wage.size();double res = 0, totalq = 0; // totalqualityvector<int> h(n);for(int i = 0; i < n; i ++ )    h[i] = i;sort(h.begin(), h.end(), [&](int &a, int &b){return wage[a] * quality[b] < wage[b] * quality[a]; });for(int i = 0; i < n; i ++ )    cout << h[i] << ' ';cout << endl;priority_queue<int, vector<int>, less<int>> q; // 降序for(int i = 0; i < k - 1; i ++ ){q.push(quality[h[i]]);totalq += quality[h[i]];}for(int i = k - 1; i < n; i ++ ){q.push(quality[h[i]]);totalq += quality[h[i]];double cur = totalq / (double)quality[h[i]] * wage[h[i]];if(res == 0 || cur < res)  res = cur;totalq -= q.top();q.pop();}return res;}
};

代码2（错误）

class Solution {
public:typedef pair<double, int> PDI;double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {int n = wage.size();double res = 0, totalq = 0; // totalqualityvector<int> h(n);for(int i = 0; i < n; i ++ )    h[i] = i;sort(h.begin(), h.end(), [&](int &a, int &b){return quality[a] < quality[b];});priority_queue<PDI, vector<PDI>, less<PDI>> q; // 降序for(int i = 0; i < k - 1; i ++ ){int idx = h[i];totalq += quality[idx];q.push({(double)wage[i] / quality[i],idx});}for(int i = k - 1; i < n; i ++ ){int idx = h[i];q.push({(double)wage[idx] / quality[idx],idx});          totalq += quality[idx];auto t = q.top();cout << totalq << ' ';double cur = totalq * t.first;if(res == 0 || cur < res)   res = cur;totalq -= quality[t.second];q.pop();}return res;}
};