(nice!!!)LeetCode 2813. 子序列最大优雅度（反悔贪心）

2813. 子序列最大优雅度

思路：1.先对数组items按profit进行降序排序。
2.把前k个最大的profit选中
3.再遍历剩余的项目，看看能不能增加类别的数量。因为profit是递减的，所以只有类别的数量能增大的情况下，才考虑从选中的k个项目当中删掉重复的类别项目里面的最小profit。
细节看注释，时间复杂度0(nlogn)

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
    	//对数组items按profit进行降序排序
        vector<pair<int ,int>> v;
        for(int i=0;i<items.size();i++){
            v.push_back({items[i][0],items[i][1]});
        }
        sort(v.begin(),v.end(),greater<pair<int ,int>>());
        //sum记录选中的k个项目里的profit之和
        long long sum=0;
        //记录最大优雅度
        long long mx=0;
        //cls记录选中的k个项目里的类别
        unordered_set<int> cls;
        //st记录选中的k个项目里:重复类别的profit,方便后续进行反悔贪心
        stack<int> st;
        for(int i=0;i<v.size();i++){
        	//当选中的项目数量不超过k时
            if(i<k){
            	//sum记录选中项目里的profit之和
                sum+=v[i].first;
                //如果这个类别已经被选过，那么就需要放到栈st里，方便后续的反悔贪心
                if(cls.count(v[i].second)){
                    st.push(v[i].first);
                }else{
                    cls.insert(v[i].second);
                }
            }else{
            	//当前项目的类别没有被选过，且栈st里的元素不空（就是选中的k个项目当中有重复类别，这里就可以进行反悔贪心）
                if(cls.count(v[i].second)==0&&st.size()){
                    sum-=st.top();
                    sum+=v[i].first;
                    st.pop();
                    cls.insert(v[i].second);
                }
            }
            long long tmp=sum+(long long)cls.size()*cls.size();
            mx=max(mx,tmp);
        }

        return mx;
    }
};