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