受标签影响的最大值 图解题解

两条上限夹着，怎么把选中的值堆到最大

给两个一样长的数组 values 和 labels，第 i 个项有个值 values[i] 和标签 labels[i]。挑一批项，守两条线：总共最多挑 numWanted 个，同一个标签最多挑 useLimit 个；在这之内让挑中的值加起来最大。题面例子 values=[5,4,3,2,1]、labels=[1,1,2,2,3]、numWanted=3、useLimit=1，答案 9=5+3+1。

光盯着大值往篮子里塞，会撞上哪堵墙

你自然想先把最大的几个抓走。可 values=[5,4,3,2,1] 里最大的 5 和次大的 4 都挂着标签 1，而 useLimit=1 只准标签 1 出一个。真按值一路抢，抢到 4 就得刹住，否则会得到标签 1 拿两个的非法结果、和虚高。拿够 numWanted 就不能再要。排个大小照单全收行不通。

为什么排完序还能边扫边挑，不用回头反悔

办法是把所有项按值从大到小排一遍，再从最大的往下看。看到一个项，先查它的标签还有没有名额：没满就收进来、值加进答案，满了就跳过；总数够了 numWanted 就收手。它成立在于：同一个标签能占的名额有限，就该留给值大的；排序保证先遇到的最大，后面同标签只会更小，跳过不亏。

一个哈希表，同时管住标签和总数两条线

扫描时备一张计数表，也就是一个哈希表，记每个标签选了几个。轮到某个项，设它的标签是 l：只要 cnt[l]＜useLimit 就选它，cnt[l] 加一、num 加一、ans 加上这个值；num 一等于 numWanted 就立刻停。cnt[l] 已等于 useLimit 的项直接略过，它后面同标签的更小值也轮不上。两条上限各查各的：标签看 cnt[l]，总数看 num，互不打架。

拿 [5,4,3,2,1] 按两上限逐个筛出 9

把每项的值与标签配对，按值从大到小排，得到 (5,1)、(4,1)、(3,2)、(2,2)、(1,3)，开头 ans=0、num=0。(5,1)：标签 1 有名额 0＜1，收下，ans=5、num=1、cnt[1]=1。(4,1)：标签 1 满了 1＜1 不成立，跳过。(3,2)：标签 2 有名额 0＜1，收下，ans=8、num=2。(2,2)：标签 2 满了，跳过。(1,3)：标签 3 有名额 0＜1，收下，ans=9、num=3，num 到 numWanted=3，停。最后 ans=9，正是 5+3+1。

排序占大头 O(n log n)，两个方向别栽进去

时间上，把 n 个项排序是 O(n log n)，是主导项；之后扫一遍、每项做几次常数哈希操作是 O(n)，合起来 O(n log n)。空间上，配对数组 O(n)、标签计数表也不超过 O(n)。

排序方向是第一道坎：按值从小到大排的话，先被塞进名额的全是小值，等大值轮到时标签或总数早满了，和只会偏小，所以一定得从大到小。停手条件是第二道：num 到了 numWanted 还不刹车，接着扫要么白算，要么把总数撑破。还有个极端 useLimit=0，谁都开不了张，答案就是 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def largestValsFromLabels(
        self, values: List[int], labels: List[int], numWanted: int, useLimit: int
    ) -> int:
        ans = num = 0
        cnt = Counter()
        for v, l in sorted(zip(values, labels), reverse=True):
            if cnt[l] < useLimit:
                cnt[l] += 1
                num += 1
                ans += v
                if num == numWanted:
                    break
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        int n = values.size();
        vector<pair<int, int>> pairs(n);
        for (int i = 0; i < n; ++i) {
            pairs[i] = {-values[i], labels[i]};
        }
        sort(pairs.begin(), pairs.end());
        unordered_map<int, int> cnt;
        int ans = 0, num = 0;
        for (int i = 0; i < n && num < numWanted; ++i) {
            int v = -pairs[i].first, l = pairs[i].second;
            if (cnt[l] < useLimit) {
                ++cnt[l];
                ++num;
                ans += v;
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; ++i) {
            pairs[i] = new int[] {values[i], labels[i]};
        }
        Arrays.sort(pairs, (a, b) -> b[0] - a[0]);
        Map<Integer, Integer> cnt = new HashMap<>();
        int ans = 0, num = 0;
        for (int i = 0; i < n && num < numWanted; ++i) {
            int v = pairs[i][0], l = pairs[i][1];
            if (cnt.getOrDefault(l, 0) < useLimit) {
                cnt.merge(l, 1, Integer::sum);
                num += 1;
                ans += v;
            }
        }
        return ans;
    }
}