Skip to main content

20240613 2813 - Hard - Greedy

2813. Maximum Elegance of a K-Length Subsequence

输入：items <1, 2>, <1, 3>, <2, 3>

目标为计算 k 个项目的 elegance：total_profit + len(vis) * len(vis)

  1. 把利润从大到小排序
  2. 遍历利润
    1. 累加前 k 个项目的利润，同时计算当前类别墅，计算重复类别的 profit
    2. 如果当前 item 的类别是之前没有的，且当前存在重复类别（如果不存在，根本无需换）
      1. 把重复类别最小利润的 item 取出，选择当前 item
    3. 如果当前 item 的类别是重复的，则不可能使得 elegance 增加（因为 profit 变小，而 len(vis) 不变）
    4. 更新 ans
class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        items.sort(key=lambda p: -p[0])  # 把利润从大到小排序
        ans = total_profit = 0
        vis = set()
        duplicate = []  # 重复类别的利润
        for i, (profit, category) in enumerate(items):
            if i < k:
                total_profit += profit  # 累加前 k 个项目的利润
                if category not in vis:
                    vis.add(category)
                else:  # 重复类别
                    duplicate.append(profit)
            elif duplicate and category not in vis:  # 之前没有的类别
                vis.add(category)  # len(vis) 变大
                total_profit += profit - duplicate.pop()  # 用最小利润替换
            # else: 比前面的利润小，而且类别还重复了，选它只会让 total_profit 变小，len(vis) 不变，优雅度不会变大
            ans = max(ans, total_profit + len(vis) * len(vis))
        return ans
Last updated on