第71场双周赛

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

首先，我们先来看一个问题：

有$a_1, a_2, ...., a_n n$个数和 $b_1, b_2, …, b_n n$个权重，如何组合，使得其值最小?

即找到一种组合使得$a_{i_1} * b_{i_1} + a_{i_2} * b_{i_2} + .... + a_{i_n} * b_{i_n}$
最小（$b_i$中可能有值相同的）

我们将$b_1, .., b_n$ 按从大到小排序，依次考虑其对应的组合。

• 我们使用贪心法来解决

• 最优解 = 给$a_i$中最小的分配给权重最大的 + 剩下的a和b的最优组合

• 证明: 如果一个解没有将$a_i$中最小值分配给权重最大的，我们交换后可以获得一个更小的解。

对于接下来的问题，我们就对不同的分解形式构造出最小的值了，当然我们还可以进一步的找到最小值在哪一种分解形式中或哪一种权重中。

四位数可以拆成以下两种

• 1 + 3形式
  • 考虑没有零的情况下，此时的最小值可以转换为一个更小的 2 + 2形式最小和
    • 将3位数的百分位移到1位数的十分位上
  • 考虑存在零的情况下，存在一个2 + 2的和最小值相同
    • 此时3位数的百分位为0，将它移到1位数的十分位上
  • 综上所述， 1 + 3的最小值 >= 2 + 2的最小值
• 2 + 2形式
  • 最小值就是将小的数放在十分位上，大的数放在个位数上

class Solution {
public:
    int minimumSum(int num) {
        int digit[4], i = 0;
        while(num != 0) {
            digit[i++] = num%10;
            num /= 10;
        }
        sort(digit, digit+4);
        return (digit[0] + digit[1]) * 10 + digit[2] + digit[3];
    }
};

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

模拟，遍历

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        int n = nums.size();
        vector<int> ans(n, pivot);
        int idx = n - 1;
        for(int i = n - 1; i >= 0; --i)
            if(nums[i] > pivot) ans[idx--] = nums[i];
        idx = 0;
        for(int i = 0; i < n; ++i)
            if(nums[i] < pivot) ans[idx++] = nums[i];
        return ans;
    }
};

2162. 设置时间的最少代价

• targetSeconds
  • -> MM:HH HH < 60
  • -> MM:HH 60 <= HH <= 99
• 模拟

给定一个targetSeconds最多有两种表示形式，因为前缀0会自动补全，我们从第一个非零位开始计算即可。

class Solution {
public:
    int cal_cost(int minutes, int seconds, int moveCost, int pushCost,int startAt){
        if(minutes < 0 || minutes > 99 || seconds < 0 || seconds > 99) return INT_MAX;
        vector<int> time = {minutes/10, minutes%10,  seconds/10, seconds%10};
        int i = 0, cost = 0;
        for(; i < 4 && time[i] == 0; ++i);
        while(i < 4) {
            if(startAt == time[i])
                cost += pushCost;
            else {
                cost += moveCost;
                cost += pushCost;
                startAt = time[i];
            }
            ++i;
        }
        return cost;
    }
    int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) {
        int minutes = targetSeconds/60, seconds = targetSeconds%60;
        return min(cal_cost(minutes, seconds,moveCost,pushCost,startAt), cal_cost(minutes -1,seconds + 60, moveCost,pushCost,startAt));
    }
};

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

• 枚举分割点
• 此时最小的值是显然的
  • 左侧最小值 = 分割点左侧值总和 - 多余点最大值
  • 右侧最大值=分割点右侧总和-多余点最小值
  • 最小值=左侧最小值-右侧最大值

class Solution {
public:
    long long minimumDifference(vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>> p1; // 小顶堆
        priority_queue<int, vector<int>, less<int>> p2; // 大顶堆

        int n = nums.size()/3;
        long long max_pre[n+1], min_pre[n+1];
        max_pre[0] = 0,min_pre[0] = 0;
        for(int i = 0; i < 2 * n; ++i) {
            p2.push(nums[i]);
            p1.push(nums[3 * n - 1 - i]);
            if(i >= n) {
                max_pre[i - n + 1] = max_pre[i-n] + p2.top();
                min_pre[i - n + 1] = min_pre[i- n] + p1.top();

                p2.pop();
                p1.pop();
            }
        }
        long long pre[3 * n+1];
        pre[0] = 0;
        long long ans = 10e15;
        for(int i = 1;i <= 3 * n; ++i) pre[i] = pre[i-1] + nums[i-1];
        for(int i = n-1; i < 2 * n; ++i) {
            long long left = pre[i+1] - pre[0] - max_pre[i-n+1];
            long long right = pre[3 * n] - pre[i + 1] - min_pre[2 * n - i - 1];
            if(left - right < ans) ans = left - right;
        }
        return ans;
    }
};