第71周双周赛

5984. 拆分数位后四位数字的最小和

class Solution {
public:
    int minimumSum(int num) {
        vector<int> vec;
        int t = num;
        while (t) {
            vec.push_back(t % 10);
            t /= 10;
        }
        sort(vec.begin(), vec.end());
        int zero = count(vec.begin(), vec.end(), 0);
        if (zero == 3) {
            return vec[3];
        } else if (zero == 2) {
            return vec[2] + vec[3];
        } else if (zero == 1) {
            if (vec[2] > vec[3]) return vec[1] * 10 + vec[3] + vec[2];
            return vec[1] * 10 + vec[2] + vec[3];
        } else {
            return vec[0] * 10 + vec[2] + vec[1] * 10 + vec[3]; 
        }
        return 0;
    }
};

5985. 根据给定数字划分数组

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> vec1;
        for (auto num: nums) 
            if (num < pivot) vec1.push_back(num);
        vector<int> vec2;
        for (auto num: nums) 
            if (num > pivot) vec2.push_back(num);
        int tot = count(nums.begin(), nums.end(), pivot);
        vector<int> res;
        for (auto i: vec1) res.push_back(i);
        for (int i = 0; i < tot; i ++) res.push_back(pivot);
        for (auto i: vec2) res.push_back(i);
        return res;
    }
};

5986. 设置时间的最少代价

class Solution {
public:
    /*
        分类讨论
            因为秒数的范围[0,99], 分两种场景讨论:
            a. mins = target / 60, secs = target % 60;
            b. mins = target / 60 - 1, secs = target % 60 + 60;
            将mins*100+secs转为字符串进行处理, 求出花费的时间即可;
    */
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        int mins = targetSeconds / 60, secs = targetSeconds % 60;
        int ans1 = calTime(startAt, moveCost, pushCost, mins, secs);
        int ans2 = calTime(startAt, moveCost, pushCost, mins - 1, secs + 60);
        return min(ans1, ans2);
    }

    int calTime(int startAt, int moveCost, int pushCost, int mins, int secs) {
        if (mins < 0 || mins > 99 || secs > 99) {
            return INT_MAX;
        }
        string s = to_string(mins * 100 + secs);
        int ans = 0;
        for (int i = 0; i < s.size(); i ++) {
            if (s[i] - '0' == startAt) {
                ans += pushCost;
            } else {
                ans += pushCost + moveCost;
            }
            startAt = s[i] - '0';
        }
        return ans;
    }
};

5987. 删除元素后和的最小差值

class Solution {
public:
    /*
        枚举i为分界点，维护0-i内长度为n / 3 的最小值，i + 1 - n - 1内长度为n / 3的最大值
    */
    long long minimumDifference(vector<int>& nums) {
        int n = nums.size(), k = n / 3;

        vector<long long> s1(n, 0); 
        priority_queue<int> small; // 大根堆，维护0 - i内的最小值
        for (int i = 0; i < 2 * k; i ++) {
            s1[i] = (i > 0) ? s1[i - 1] : 0;
            small.push(nums[i]);
            s1[i] += nums[i];
            if (small.size() > k) {
                s1[i] -= small.top();
                small.pop();
            }
        }

        vector<long long> s2(n, 0);
        priority_queue<int, vector<int>, greater<int>> big; // 小根堆，维护 i + 1 - n - 1内的最大值
        for (int i = n - 2; i >= k - 1; i --) { 
            // 注意这里是n - 2的原因是，下面计算答案是从 k - 1 ~ 2 *k - 1，如果为n-1，会多算一个数进来
            // 例如 1 2 3 4 5 6  ，n-2会使得下标为1的位置s[1] 表示 后4个数中最大值，n-1则表示5个数了
            s2[i] = s2[i + 1];
            big.push(nums[i + 1]);
            s2[i] += nums[i + 1];
            if (big.size() > k) {
                s2[i] -= big.top();
                big.pop();
            }
        }
        
        long long res = 1e15;
        for (int i = k - 1; i < 2 * k; i ++) {
            res = min(res, s1[i] - s2[i]);
        }
        return res;
    }
};