$\large\color{orange}{比赛入口：}$$\color{orange}{LeetCode331}$$\large\color{orange}{周赛}$

$\large\color{green}{2558. 从数量最多的堆取走礼物}$

模拟，时间复杂度：$O(knlogn)$

class Solution {
public:
    typedef long long ll;
    long long pickGifts(vector<int>& gifts, int k) {
        ll res = 0;
        sort(gifts.begin(), gifts.end(), greater<int>());
        while(k -- ){
            int t = sqrt(gifts[0]);
            if(t * t > gifts[0])    t -- ;
            gifts[0] = t;
            sort(gifts.begin(), gifts.end(), greater<int>());
        }
        for(auto x : gifts) res += x;
        return res;
    }
};

$\large\color{orange}{2559. 统计范围内的元音字符串数}$

前缀和，时间复杂度：$O(n)$

class Solution {
public:
    static const int N = 1E5 + 10;
    int s[N];
    bool is_(char c){
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
    bool check(string s){
        int n = s.size();
        return is_(s[0]) && is_(s[n - 1]);
    }
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        memset(s, 0, sizeof s);
        reverse(words.begin(), words.end());
        words.push_back("");
        reverse(words.begin(), words.end());
        int n = words.size();
        for(int i = 1; i < n; i ++ )    s[i] += s[i - 1] + check(words[i]);
        vector<int> res;
        for(auto q : queries)   res.push_back({s[q[1] + 1] - s[q[0]]});
        return res;
    }
};

$\large\color{orange}{2560. 打家劫舍 IV}$

二分+贪心，时间复杂度：$O(nlogn)$

class Solution {
public:
    int n;
    bool check(int x, vector<int>& nums, int k){
        int cnt = 0;
        int pre = -2;
        for(int i = 0; i < n; i ++ ){
            if(i - pre == 1)    continue;
            if(nums[i] > x) continue;
            cnt ++ ;
            pre = i;
        }
        return cnt >= k;
    }
    int minCapability(vector<int>& nums, int k) {
        n = nums.size();
        int l = 1, r = 1e9 + 1;
        while(l < r){
            // cout << "----" << endl;
            int mid = l + r >> 1;
            if(check(mid, nums, k)) r = mid;
            else    l = mid + 1;
        }
        return l;
    }
};

$\large\color{red}{2561. 重排水果}$

Map + 贪心，时间复杂度：$O(nlogn)$

class Solution {
public:
    unordered_map<int, int> mp1, mp2;
    typedef pair<int, int> pii;
    map<pii, bool> nmp1, nmp2;
    typedef long long ll;
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        int minv1 = 0x3f3f3f3f, minv2 = 0x3f3f3f3f; 
        for(auto x : basket1)   mp1[x] ++ , minv1 = min(minv1, x);
        for(auto x : basket2)   mp2[x] ++ , minv2 = min(minv2, x);
        int minv = min(minv1, minv2);
        for(auto it = mp1.begin(); it != mp1.end(); it ++ ){
            int x = it->first;
            if(mp2.find(x) != mp2.end()){
                int sub = min(it->second, mp2[x]);
                mp1[x] -= sub;
                mp2[x] -= sub;
            }
        }
        vector<pii> r1, r2;
        for(auto it = mp1.begin(); it != mp1.end(); it ++ ){
            if(it->second)  r1.push_back({it->first, it->second});
        }
        bool flag = true;
        for(auto x : r1)    if(x.second % 2)   flag = false;
        if(!flag)   return -1;
        for(auto x : r1){
            int f = x.first, s = x.second;
            if(s == 1)  nmp1[{f, 1}] = true;  
            else{
                int t = s / 2;
                for(int i = 1; i <= t; i ++ )   nmp1[{f, i}] = true;
            }
        }

        for(auto it = mp2.begin(); it != mp2.end(); it ++ ){
            if(it->second)  r2.push_back({it->first, it->second});
        }
        for(auto x : r2)    if(x.second % 2)   flag = false;
        if(!flag)   return -1;

        for(auto x : r2){
            int f = x.first, s = x.second;
            if(s == 1)  nmp1[{f, 1}] = true;
            else{
                int t = s / 2;
                for(int i = 1; i <= t; i ++ )   nmp2[{f, i}] = true;
            }
        }

        int times = nmp1.size();
        ll res = 0;
        while(times -- ){
            int x1 = nmp1.begin()->first.first, x2 = nmp2.begin()->first.first;
            if(x1 <= x2){
                res += min(minv * 2, x1);
                nmp1.erase(nmp1.begin());
                auto it = nmp2.end();
                it -- ;
                nmp2.erase(it);
            }else{
                res += min(minv * 2, x2);
                nmp2.erase(nmp2.begin());
                auto it = nmp1.end();
                -- it;
                nmp1.erase(it);
            }
        }
        return res;
    }
};