leetcode 第280场周赛

T1 得到 0 的操作数

水题

T2 使数组变成交替数组的最少操作数

题意

如果一个数组为交替数组，那么它奇数下标子序列值相同均为 $x$、偶数下标子序列值相同均为 $y$ ，且 $x \neq y$ 。给出任意一个数组，问至少几次单点修改操作才能使它变成交替数组。

做法

考虑贪心，不论奇数子列还是偶数子列，保留出现次数最大的那个数 $fx$ 和 $fy$，将其他数改成最大数。但还需考虑 $fx=fy$ 的情况。此时需要将出现次数第二大的数考虑进来，设奇偶子列出现次数第二大的数分别为 $sx$ 和 $sy$，答案为 $min(n - fx - sy, n - fy - sx)$ 。

代码

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<vector<int>> v(2, vector<int>(1e5 + 10, 0));
        int n = nums.size();
        for (int i = 0; i < n; i++) v[i & 1][nums[i]]++;

        int f1 = max_element(v[0].begin(), v[0].end()) - v[0].begin();
        int f2 = max_element(v[1].begin(), v[1].end()) - v[1].begin();
        if (f1 != f2) 
        {
            return n - v[0][f1] - v[1][f2];
        }

        int fv1 = v[0][f1];
        int fv2 = v[1][f2];
        v[0][f1] = 0;
        v[1][f2] = 0;
        int s1 = max_element(v[0].begin(), v[0].end()) - v[0].begin();
        int s2 = max_element(v[1].begin(), v[1].end()) - v[1].begin();
        return min(n - fv1 - v[1][s2], n - v[0][s1] - fv2);
    }
};

T3 拿出最少数目的魔法豆

题意

给你一个正整数数组，其中每个整数表示一个袋子里装的魔法豆的数目。请你从每个袋子中拿出一些豆子（也可以不拿出），使得剩下的非空袋子中魔法豆的数目相等。求需要拿出魔法豆的最少数目。

做法

去掉空袋子之后，最优解是使得每一个非空袋子的数量减到最小的那一个。

拿走最少，等价于剩下最多。

数组每个数的顺序对结果没有影响。

考虑排序，再从前向后枚举，把之前的袋子删空，当前袋子 $beans[i]$ 即为非空袋子中最小的那个，当前之后的袋子里的值，需要被减小到这个最小袋子的值。剩下的豆子数量即为 $beans[i] * (n - i)$，更新答案。

代码

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        using ll = long long;
        int n = beans.size();
        sort(beans.begin(), beans.end());
        ll ans = 0;
        ll sum = accumulate(beans.begin(), beans.end(), 0LL);
        for (int i = 0; i < n; i++)
        {
            ans = max(ans, beans[i] * ll(n - i));
        }
        return sum - ans;
    }
};

T4