2813. 子序列最大优雅度 Hard

给你一个长度为 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

题目大意：计算从数组中选k个元素可以获得的最大优雅度。

分析：

（1）在不考虑category的情况下，profit越大优雅度越大，因此可以将数组按profit降序排序，此时前k个数字即可组成最大优雅度；

（2）在（1）的情况下，进一步考虑category。由于第k+1个元素的profit小于前k个元素，若该元素的category在前k个元素中已经出现过，则用该元素替换前面的一个元素必然会导致total_profit变小，而distinct_categories不变，所以不选择将该元素；若该元素的category第一次出现，则用该元素替换前面的一个元素时有两种情况，若被替换的元素的category只出现过一次，则total_profit变小，而distinct_categories不变，若被替换的元素的category是冗余的，则total_profit变小，而distinct_categories增加，可能会使优雅度增加；

（3）由（2）可得出结论，要想选择后面的元素来替换前面k个元素，所选元素的category必须第一次出现，且被替换的元素的category必须冗余，同时为了让total_profit变小的程度最小，被替换的元素的profit必须在category冗余的所有元素中是最小的；

（4）接下来进一步考虑，若第k+1个元素的category第一次出现，并选择它替换了前k个元素中category冗余且profit最小的元素ele，且第k+2个元素的category也是第一次出现，则此时应该用第k+2个元素替换原先k个元素（包含元素ele）中的元素，还是替换修改后的k个元素（包含第k+1个元素）中的元素。①若替换原先的k个元素，由于ele还是category冗余且profit最小的元素，因此元素ele被第k+2个元素替换，而此替换结果与元素ele被第k+1个元素替换的结果相比，distinct_categories相同，但total_profit变小了，因此第一种替换方式只会导致优雅度更小；②若替换修改后的k个元素，虽然total_profit变小了，但distinct_categories又增加了，可能导致优雅度数提高，因此选择替换修改后的k个元素；

（5）根据上述推导，可以得到解决方案：对数组按profit降序排序，并计算前k个元素的优雅度ans，同时用哈希表set保存前k个元素中出现过的category以及用单调递减栈stack保存所有category冗余的元素的profit。然后遍历后面所有元素，若元素ele的category出现过，则不选择该元素；若ele的category第一次出现，则选择该元素，并将category加入到set中，即set.insert(ele[1])，同时用该元素ele替换stack的栈顶元素，即total_profit=total_profit-stack.top()+ele[0];++distinct_categories；stack.pop()，再维护ans的值，即ans=max(ans,total_profit+distinct_categories*distinct_categories)。当stack中的元素全都弹出栈时，distinct_categories=k，再往后遍历也无法增加distinct_categories的值，因此结束遍历。

class Solution {
public:long long findMaximumElegance(vector<vector<int>>& items, int k) {int N=items.size(),i,cg,pf;long long ans,tProfit=0,tCategories=0;unordered_set<int> s;vector<int> stack;stack.reserve(k);sort(items.begin(),items.end(),[&](vector<int>& v1,vector<int>& v2){return v1[0]>v2[0];});for(i=0;i<k;++i){tProfit+=(pf=items[i][0]);if(s.find(cg=items[i][1])==s.end()){s.insert(cg);++tCategories;}else stack.emplace_back(pf);}ans=tProfit+tCategories*tCategories;for(int rest=stack.size();i<N&&rest;++i){cg=items[i][1];if(s.find(cg)==s.end()){s.insert(cg);++tCategories;tProfit-=stack[rest-1]-items[i][0];ans=max(ans,tProfit+tCategories*tCategories);--rest;}}return ans;}
};