这场比赛感觉比较典型，遇到了以前刷过的题hh，记录一下

5561. 获取生成数组中的最大值

模拟

class Solution {
public:
    int getMaximumGenerated(int n) {
        if(n == 0) return 0;
        vector<int> nums(n + 1);
        nums[0] = 0, nums[1] = 1;
        for(int i = 2;i <= n;i ++ )
        {
            if(i % 2 == 0) nums[i] = nums[i / 2];
            else nums[i] = nums[i / 2] + nums[i / 2 + 1];
        }
        sort(nums.begin(),nums.end());

        return nums.back();
    }
};

5562. 字符频次唯一的最小删除次数 ————————类似题–AcWing1242. 修改数组
单链表式并查集
往前找到下一个没有出现的数字，对答案贡献为 当前数值 - 祖宗节点的差

const int N = 1e5 + 10;

int p[N];

int find(int x)
{
    if(p[x] != x) return p[x] = find(p[x]);
    return p[x];
}

class Solution {
public:
    int minDeletions(string s) {
        int n = s.size();
        unordered_map<char,int> cnt;
        for(auto c : s) cnt[c] ++;

        for(int i = 0;i<=n;i++) p[i] = i;
        long long res = 0;
        for(auto c : cnt)
        {
            int num = c.second;
            cout << num << endl;
            int px = find(num);
            p[px] = max(0,p[px] - 1);
            res += num - px;
        }

        return res;
    }
};

5563. 销售价值减少的颜色球
当时做法是从最大数值一个一个往下减，超时了，数值最大到1e9,应该要直接统计一段，不会，等题解

5564. 通过指令创建有序数组
树状数组
当时以为是最优化问题，后来发现依次插入，直接用树状数组统计两边的最小值。
如果是任意插入会是怎么样呢？

const int N = 1e5 + 10;

int mod = 1e9 + 7;

int tr[N];

int lowbit(int x)
{
    return x & -x;
}

int query(int x)
{
    int res = 0;
    for(int i = x;i ;i -= lowbit(i)) res += tr[i];
    return res;
}

void add(int x)
{
    for(int i = x;i <= N;i += lowbit(i)) tr[i] += 1;
}



class Solution {
public:
    int createSortedArray(vector<int>& ins) {
        memset(tr,0,sizeof tr);
        long long res = 0;
        for(auto x : ins)
        {
            // int l = query(x - 1), r= query(N - 1) - query(x);
            // cout << l << " " << r << endl;
            res += min(query(x - 1), query(N - 1) - query(x));
            add(x);
            res %= mod;
        }

        return res;
    }
};