LeetCode 5359. 最大的團隊表現值(貪心)

• 2020 年 3 月 17 日
• 筆記

題目鏈接：https://leetcode-cn.com/problems/maximum-performance-of-a-team/

       首先我們對n個人進行排序，優先效率從大到小，然後我們維護一個堆(set或者priority_queue都可以)，堆中每次維護k個值，也就是我們所要選擇的k個人。那麼對於這前k個人來說的團隊表現值就是sum*v[k-1].efficiency，那麼對於下一個人來說，他是第k+1個將他加入到堆中，然後我們刪去堆中speed最小的人，由於efficiency是從大到小排序，那麼刪除的這個人的efficiency一定是大於這個第k+1個人的，所以不需要去考慮刪除的efficiency，那麼此時的團隊表現值就是sum*v[k].efficiency，就這樣遍歷到最後維護一個最大團隊表現值就好了。

AC程式碼：

class Solution {  public:      const int mod = 1e9 + 7;      vector<pair<int,int> > v;      typedef pair<int,int> p;      multiset<int> s;      int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {          for(int i=0;i<n;i++){              v.push_back(p(speed[i], efficiency[i]));          }          sort(v.begin(), v.end(), [](const pair<int,int> a, const pair<int,int> b){              if(a.second == b.second) return a.first > b.first;              return a.second > b.second;          });          long long sum = 0;          long long ans = 0;          for(int i=0;i<n;i++){              sum += v[i].first;              s.insert(v[i].first);              if(s.size() > k){                  sum -= *s.begin();                  s.erase(s.begin());              }              ans = max(ans, sum * v[i].second);          }          return ans % mod;      }  };