康复训练 · M-071的甲板

写在前面：已经快一年没coding了，所以打算利用这一个月时间进行一个手感的找回，也好为打下基础

2023.8.6

leetcode 6953

脑筋急转弯，正难则反

leetcode 2813

一开始没想到，看题解后知道是反悔贪心，然后就写了一个错误答案

class Solution {
public:

    struct cmp2{
        bool operator()(const pair<int, int> &a, const pair<int, int> &b){
                return a.first > b.first;
        }
    };

    pair<int,int> s[100010];
    priority_queue< pair<int,int> , vector<pair<int,int> >,cmp2 > p;
    int n,tmp=0,lx=0,sum[100010];

    static bool cmp1(pair<int,int> a,pair<int,int> b){
        if(a.first==b.first) return a.second<b.second;
        return a.first>b.first; 
    }

    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        n=items.size();

        for(int i=1;i<=n;i++){
            s[i]=make_pair(items[i-1][0],items[i-1][1]);
        }

        sort(s+1,s+1+n,cmp1);

        for(int i=1;i<=k;i++){
            if(sum[s[i].second]==0){
                lx++;
                sum[s[i].second]=1;
                tmp+=s[i].first;
            }else{
                sum[s[i].second]++;
                tmp+=s[i].first;
                p.push(make_pair(s[i].first,s[i].second));
            }
        }

        tmp+=lx*lx;

        if(p.empty()) return tmp;

        for(int i=k+1;i<=n;i++){
            if(sum[s[i].second]){continue;}
            int tmp1=tmp;
            while(!p.empty()&&sum[p.top().second]<=1) p.pop();
            if(p.empty()) return tmp;
            auto t=p.top();
            tmp1-=t.first;
            tmp1+=s[i].first;
            tmp1-=lx*lx;
            tmp1+=(lx+1)*(lx+1);
            if(tmp1>tmp){
                lx++;
                tmp=tmp1;
                p.pop();
                sum[t.second]--;
                sum[s[i].second]++;
            }
        }

        return tmp;
    }
};