Description
公司有编号为
1到n的n个工程师，给你两个数组speed和efficiency，其中speed[i]和efficiency[i]分别代表第i位工程师的速度和效率。请你返回由最多k个工程师组成的 最大团队表现值 ，由于答案可能很大，请你返回结果对10^9 + 7取余后的结果。团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
Examples Input
n = 6
speed = [2,10,3,1,5,8]
efficiency = [5,4,3,9,7,2]
k = 2
Examples Output
60
思路
记得 leetcode 每场周赛至少有一个 dp 题，可能太久没打了，形势变了 QAQ
这道题乍一看「团队表现值」的计算中有着「效率值中的最小值」这一因素，那我们从这一点入手。
思考假设当前已经确定了效率的最小值 $x$，那么员工便可以从效率大于等于 $x$ 的人中最多找 speed 前 $k$ 个即可。
而直接循环处理这一个过程显然时间复杂度是 $O(n^2)$ 的不可取，这里还有一个递推的因素在里面，即工作效率大于 $x$ 的人必定工作效率大于 $x-1$。
于是我们按照工作效率从大到小给所有人排序，然后开始遍历。
使用 multiset 维护当前所有工作效率大于等于 $x$ 的人的 speed，当然用优先队列维护也可以。
在每一次处理工作效率为 $x$ 的循环中，首先将工作效率为 $x$ 的人的 speed 加入到 multiset 里（efficiency 大于 $x$ 之前的循环已经加过了），然后调整 multiset 的内容，删除 speed 最小的元素直到其容量小于等于 $k$，这里我用了 tmpadd 维护了 multiset 中所有元素的和。
再就找每个循环处理结果的最大值便好了，记得取模，当前「团队表现值」等于 $x \times tmpadd$。
需要注意的一点：题中的最大值指 $x \times tmpadd$ 的最大值再取模，而不是 $x \times tmpadd$ 取模的最大值。
AC 代码
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const double eps = 1e-8;
class Solution {
public:
int maxPerformance(int n, vector<int> &speed, vector<int> &efficiency,
int k) {
multiset<int> st;
map<int, vector<int>> mp;
for (int i = 0; i < n; i++) {
mp[efficiency[i]].push_back(speed[i]);
}
long long ans = 0, tmpadd = 0; // tmpadd 为 st 中元素之和（员工速度和）
for (auto i = mp.rbegin(); i != mp.rend(); i++) {
for (auto s : i->second) {
st.insert(s);
tmpadd += s;
}
int stsize = max(0, (int)st.size() - k);
for (int j = 0; j < stsize; j++) {
tmpadd -= *st.begin();
st.erase(st.begin());
}
long long tmp = i->first * tmpadd;
ans = max(ans, tmp);
}
return ans % mod;
}
};
