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

$\large\color{green}{2600. K 件物品的最大和}$

数学，时间复杂度：$O(1)$

class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if(k <= numOnes)    return k;
        if(k <= numOnes + numZeros) return numOnes;
        return numOnes - (k - numOnes - numZeros);
    }
};

$\large\color{orange}{2601. 质数减法运算}$

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

class Solution {
public:
    static const int N = 1010;
    set<int> st;
    void get_prime(int x){
        st.insert(2);
        for(int i = 3; i < x; i ++ ){
            bool flag = true;
            for(int j = 2; j <= i / j; j ++ ){
                if(i % j == 0){
                    flag = false;
                    break;
                }
            }
            if(flag)    st.insert(i);
        }
    }
    bool primeSubOperation(vector<int>& nums) {
        get_prime(N);
        int n = nums.size();
        for(int i = n - 2; i >= 0; i -- ){
            if(nums[i] >= nums[i + 1]){
                auto diff = *st.lower_bound(nums[i] - nums[i + 1] + 1);
                if(diff >= nums[i]) return false;
                nums[i] -= diff;
            }
        }
        return true;
    }
};

$\large\color{orange}{2602. 使数组元素全部相等的最少操作次数}$

前缀和 + 二分，时间复杂度：$O(nlogn)$

class Solution {
public:
    typedef long long ll;
    static const int N = 1E5 + 10;
    ll s[N];
    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
        sort(nums.begin(), nums.end());
        reverse(nums.begin(), nums.end());
        nums.push_back(0);
        reverse(nums.begin(), nums.end());
        memset(s, 0, sizeof s);
        int n = nums.size();
        for(int i = 1; i < n; i ++ )    s[i] += s[i - 1] + nums[i];
        vector<long long> res;
        for(auto x : queries){
            ll l = 1, r = n - 1;
            ll sum = 0;
            while(l < r){
                int mid = l + r >> 1;
                if(nums[mid] >= x)  r = mid;
                else    l = mid + 1;
            }
            if(nums[l] == x)    sum = x * l - s[l] + s[n - 1] - s[l] - x * (n - 1 - (l + 1) + 1); 
            else if(nums[l] < x)    sum =  x * (n - 1ll) - s[n - 1];//  大于x
            else    sum = x * (l - 1) - s[l - 1] + s[n - 1] - s[l - 1] - x * (n - 1 - l + 1); 
            res.push_back(sum);
        }
        return res;
    }
};

$\large\color{red}{2603. 收集树中金币}$

拓扑排序+树形DP，时间复杂度：$O(n)$

调了很多次，还是卡常了（最后一个样例没用过），不管了！

class Solution {
public:
    static const int N = 1e5 + 10, M = N * 2;
    int h[N], e[M], ne[M], idx; 
    int d[N];
    bool st[N];
    int down[N], up[N];
    int qu[N];
    int hh, tt;
    void init(){
        memset(h, -1, sizeof h);
        memset(e, 0, sizeof e);
        memset(ne, 0, sizeof ne);
        memset(d, 0, sizeof d);
        memset(st, 0, sizeof st);
        idx = 0;
        memset(down, 0, sizeof down);
        memset(up, 0, sizeof up);
        memset(qu, 0, sizeof qu);
        hh = tt = 0;
    }
    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }
    void establish(vector<vector<int>>& edges){
        for(auto edge : edges){
            int a = edge[0], b = edge[1];
            add(a, b), add(b, a);
            d[a] ++ , d[b] ++ ;
        }
    }
    void dfs_down(int u, int father){
        down[u] = 0;
        for(int i = h[u]; ~i; i = ne[i]){
            int j = e[i];
            if(j == father || st[j]) continue;
            dfs_down(j, u);

            down[u] += down[j] + 1;
        }
    }
    void dfs_up(int u, int father){
        if(father == -1)    up[u] = 0;
        else    up[u] = down[father] + up[father] - down[u];
        for(int i = h[u]; ~i; i = ne[i]){
            int j = e[i];
            if(j == father || st[j]) continue;
            dfs_up(j, u);

        }
    }
    typedef pair<int, int> pii;
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        init();
        establish(edges);
        int n = coins.size();
        for(int i = 0; i < n; i ++ ){
            if(d[i] == 1 && coins[i] == 0){
                qu[tt ++ ] = i;
                st[i] = true;
            }
        }
        while(tt != hh){
            int cur = qu[hh];
            hh ++ ;
             for(int i = h[cur]; i != -1; i = ne[i]){
                int j = e[i];
                if(st[j])   continue;
                d[j] -- ;
                if(coins[j])    continue;
                if(d[j] == 1){
                    qu[tt ++ ] = j;
                    st[j] = true;
                }   
            }
        }
        hh = tt = 0;
        for(int i = 0; i < n; i ++ ){
            if(st[i])   continue;
            if(coins[i] == 1 && d[i] == 1){
                st[i] = true;
                qu[tt ++ ] = i;
            }   
        }
        while(hh != tt){
            int len = tt - hh;
            for(int k = 0; k < len; k ++ ){
                int cur = qu[hh];
                hh ++ ;
                for(int i = h[cur]; i != -1; i = ne[i]){
                    int j = e[i];
                    if(st[j])   continue;
                    d[j] -- ;
                    if(d[j] == 1)   st[j] = true;   

                }
            }
        }


        int root = -1;
        for(int i = 0; i < n; i ++ ){
            if(!st[i]){
                root = i;
                break;
            }
        }
        if(root == -1)  return 0;
        dfs_down(root, -1);
        dfs_up(root, -1);
        int minv = 0x3f3f3f3f;
        for(int i = 0; i < n; i ++ ){
            if(!st[i])  minv = min(minv, (down[i] + up[i]) * 2);
        }
        return minv == 0x3f3f3f3f ? 0 : minv;
    }
};