【贪心】
Problem Link
我们有一个项的集合,其中第 i
项的值为 values[i]
,标签为 labels[i]
。
我们从这些项中选出一个子集 S
,这样一来:
|S| <= num_wanted
- 对于任意的标签
L
,子集S
中标签为L
的项的数目总满足<= use_limit
。返回子集S
的最大可能的 和。
Example:
示例 1:
输入:values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出:9
解释:选出的子集是第一项,第三项和第五项。
示例 2:
输入:values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出:12
解释:选出的子集是第一项,第二项和第三项。
示例 3:
输入:values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出:16
解释:选出的子集是第一项和第四项。
示例 4:
输入:values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出:24
解释:选出的子集是第一项,第二项和第四项。
Analysis
这道题目读懂了就不难(我竞赛的时候就钻牛角尖了)。
第一点要求 |S| <= num_wanted
是说选择的总数不能超过 num_wanted
第二点要求是说同一个标签下的项,选择的数量不能超过 use_limit
理解了这两点就很清楚了,这是一个简单的贪心策略能够解决的问题,只需要将其按照价值排列,优先选择价值高的即可。
下面提供一种直接实现的思路。
Solution
执行用时 :107 ms, 在所有 Java 提交中击败了44.00%的用户
内存消耗 :49.9 MB, 在所有 Java 提交中击败了100.00%的用户
|
|
复杂度分析
时间:$O(NlogN)$ $N = len(values)$
空间:$O(max{label})$