反悔贪心

LeetCode2024 6.13每日一题

LC2813. 子序列最大优雅度

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。

items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。

现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories2 计算，其中 total_profit 是子序列中所有项目的利润总和，distinct_categories 是所选子序列所含的所有类别中不同类别的数量。

你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。

用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。

**注意：**数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。

示例 1：

输入：items = [[3,2],[5,1],[10,1]], k = 2
输出：17
解释：
在这个例子中，我们需要选出长度为 2 的子序列。
其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。
子序列的总利润为 3 + 10 = 13 ，子序列包含 2 种不同类别 [2,1] 。
因此，优雅度为 13 + 22 = 17 ，可以证明 17 是可以获得的最大优雅度。 

示例 2：

输入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3
输出：19
解释：
在这个例子中，我们需要选出长度为 3 的子序列。 
其中一种方案是 items[0] = [3,1] ，items[2] = [2,2] 和 items[3] = [5,3] 。
子序列的总利润为 3 + 2 + 5 = 10 ，子序列包含 3 种不同类别 [1, 2, 3] 。 
因此，优雅度为 10 + 32 = 19 ，可以证明 19 是可以获得的最大优雅度。

示例 3：

输入：items = [[1,1],[2,1],[3,1]], k = 3
输出：7
解释：
在这个例子中，我们需要选出长度为 3 的子序列。
我们需要选中所有项目。
子序列的总利润为 1 + 2 + 3 = 6，子序列包含 1 种不同类别 [1] 。
因此，最大优雅度为 6 + 12 = 7 。

提示：

• 1 <= items.length == n <= 105
• items[i].length == 2
• items[i][0] == profiti
• items[i][1] == categoryi
• 1 <= profiti <= 109
• 1 <= categoryi <= n
• 1 <= k <= n

这道题目打开的时候，感觉就很熟悉，而且一下就想到了反悔贪心(之前做过，残存的记忆)，但是我一直在想将items按照profiti进行从小到大排序，一直陷入这个误区，想了一晚上没有想到解决的方法。(当时想法:用两个队列，一个队列存首次出现的categoryi,另一个队列存放再次出现的categoryi,然后在遍历的时候判断这个categoryi 和首次队列和再次队列的值…，最后发现控制不了首次队列与第二次出现的队列的元素交换，遗憾放弃…),只能看之前的做法，原来是要从大到小排序，遍历时更新最大值。

从大到小排序很好解决了上面的问题，只需要一个队列维护重复的categoryi ，如果当选取的元素数量超过k时，如果遇到重复的categoryi ,那必不可能选的，因为此时的profiti必然小于已经选了的profiti，当queue中有元素时，只要遇到之前没有出现的categoryi就将其加入进去，因为后面的非重复的categoryi的profiti都比此时的小。

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key=lambda e: -e[0])
        ans, su, s, q = 0, 0, set(), []
        for x, y in items:
            if len(s) + len(q) < k:
                if y in s:
                    q.append(x)
                else:
                    s.add(y)
                su += x
            else:
                if y not in s and q:
                    su -= q.pop()
                    su += x
                    s.add(y)
            ans = max(ans, len(s) * len(s) + su)
        return ans