🔗 🔴 2813. Maximum Elegance of a K-Length Subsequence 2582

tags: `Weekly Contest 357` `貪心(Greedy)` `反悔貪心` `排序(Sorting)` `雜湊表(Hash Table)` `堆積(Heap)` `堆疊(Stack)`

題意

給定一個長度為 $n$ 的二維整數陣列 $items$ 和一個整數 $k$ 。

$items[i] = [profit_i, category_i]$ ，其中 $profit_i$ 和 $category_i$ 分別表示第 $i$ 個項目的利潤和類別。

我們定義項目 子序列(Subsequence) 的 優雅度(Elegance) 為 $\text{total\_profit} + \text{distinct\_categories}^2$ ，其中 $\text{total\_profit}$ 是子序列中所有利潤的總和， $\text{distinct\_categories}$ 是選定子序列中不同類別的數量。

你的任務是找出 $items$ 中所有大小為 $k$ 的子序列中的最大優雅度，以整數表示形式返回。

注意：一個陣列的 子序列(Subsequence) 是由刪除一些元素(可能沒有)而生成的新陣列，而不改變其餘元素的相對順序。

思路：反悔貪心

基於貪心(Greedy) 的思想，可以使用一種稱為「反悔貪心」的策略來解決這個問題。

我們可以先不考慮不同類別的數量，只考慮利潤的總和，故此時利潤最大的 $k$ 個物品之利潤總和即為答案。故可以將物品按照利潤由大到小的順序排序。然後從前 $k$ 個物品開始，計算它們的總利潤與不同類別數的平方之和，作為初始的最大優雅度。

接下來，我們從第 $k+1$ 個物品開始遍歷，對於每個物品：

若這個物品所屬的種類已經出現過，那麼顯然不會增加優雅度，可以直接跳過這個物品。
否則，我們可以考慮是否替換掉已經選定的物品中的某個物品，以嘗試讓總優雅度變大。
- 若先前的物品中，沒有重複種類的物品，則替換後 $\text{total\_profit}$ 會變小，但 $\text{distinct\_categories}$ 不變，因此顯然也不會增加優雅度，可以直接跳過這個物品。
- 若先前的物品中，有重複種類的物品，則我們可以選擇重複的物品中利潤最小的那個，用這個新物品來替換它。替換後雖然 $\text{total\_profit}$ 會變小，但 $\text{distinct\_categories}$ 會增加，因此可能會增加優雅度。也就是反悔之前的選擇，重新選擇一個更好的子序列。

為此，我們可以維護一個集合 $seen$ 來記錄已經出現過的種類，以及一個陣列 $dulplicate$ 來紀錄重複出現的種類中，第二個以後的物品的利潤。在每次遍歷時，我們可以根據這兩個資料結構來判斷是否需要替換掉某個物品。由於對於 $dulplicate$ 的添加和刪除操作都是在陣列的尾部進行的，因此也可以使用堆疊(Stack)來實現。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ ，排序需要 $\mathcal{O}(n \log n)$ 時間，遍歷和操作每個物品需要 $\mathcal{O}(n)$ 時間，因此總體時間複雜度為 $\mathcal{O}(n \log n)$ 。
空間複雜度： $\mathcal{O}(n)$ ，使用了 $seen$ 集合來記錄已經出現過的種類，以及 $dulplicate$ 陣列來存儲相同種類的利潤。

class Solution:
    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
        n = len(items)
        items.sort(key= lambda x : x[0], reverse=True)
        cur = 0
        seen = set() # 已經出現過的種類
        dulplicate = [] # 所有種類中，第二個以後的物品，利潤由大到小

        for i in range(min(k, n)): # 先加入前 k 個物品
            profit, category = items[i]
            cur += profit
            if category in seen: # 重複的種類
                dulplicate.append(profit)
            else: # 新的種類
                seen.add(category)

        ans = cur + len(seen) * len(seen) # 初始化答案為前 k 個物品的利潤 + 種類數量的平方
        for i in range(k, n):
            profit, category = items[i]
            # 有新的種類，且之前有重複種類的物品，則取代最小的重複物品，嘗試看看會不會讓答案變大
            if dulplicate and category not in seen:
                seen.add(category)
                cur += profit - dulplicate.pop() # 去除重複種類的物品中，利潤最小的
                ans = max(ans, cur + len(seen) * len(seen)) # 更新答案
        return ans

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        int n = items.size();
        sort(items.begin(), items.end(), greater<vector<int>>());
        long long ans = 0, cur = 0, sz = 0;
        unordered_set<int> seen; // 已經出現過的種類
        vector<int> dulplicate; // 所有種類中，第二個以後的物品，利潤由大到小
        for (int i = 0; i < min(k, n); i++) { // 先加入前 k 個物品
            int profit = items[i][0], category = items[i][1];
            cur += profit;
            if (seen.count(category)) dulplicate.push_back(profit); // 重複的種類
            else seen.insert(category); // 新的種類
        }
        sz = seen.size();
        ans = cur + sz * sz; // 初始化答案為前 k 個物品的利潤 + 種類數量的平方
        for (int i = k; i < n; i++) {
            int profit = items[i][0], category = items[i][1];
            // 有新的種類，且之前有重複種類的物品，則取代最小的重複物品，嘗試看看會不會讓答案變大
            if (!dulplicate.empty() && !seen.count(category)) {
                seen.insert(category);
                cur += profit - dulplicate.back(); // 去除重複種類的物品中，利潤最小的
                dulplicate.pop_back();
            }
            sz = seen.size();
            ans = max(ans, cur + sz * sz); // 更新答案
        }
        return ans;
    }
};