leetcode 第280场周赛

前言：我是SB

T2

给你一个下标从 0 开始的数组 nums ，该数组由 n 个正整数组成。

如果满足下述条件，则数组 nums 是一个 交替数组 ：

nums[i - 2] == nums[i] ，其中 2 <= i <= n - 1 。
nums[i - 1] != nums[i] ，其中 1 <= i <= n - 1 。
在一步 操作 中，你可以选择下标 i 并将 nums[i] 更改 为 任一 正整数。

返回使数组变成交替数组的 最少操作数 。

分析：

分别统计奇数位，偶数位出现次数最多的数

但是这样有可能这俩数相同，我们分别找一下两个数组里的次大值就可以了（非严格次大值）

一个函数max_element(v.begin(), v.end()) - v.begin()这个函数非常好用，可以直接找到最大值的下标

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        vector<int> ji(100001, 0);
        vector<int> ou(100001, 0);
        int n = nums.size();
        for(int i = 0; i < nums.size(); i ++ ) {
            if(i & 1) ji[nums[i]] ++;
            else ou[nums[i]] ++;
        }
        int max1 = 0, max2 = 0;
        max1 = max_element(ji.begin(), ji.end()) - ji.begin();
        max2 = max_element(ou.begin(), ou.end()) - ou.begin();
        if(max1 != max2) {
            return n - (ji[max1] + ou[max2]);
        } else {
            int tmp_max1 = ji[max1];
            int tmp_max2 = ou[max2];
            ji[max1] = ou[max2] = 0;
            int amax1 = max_element(ji.begin(), ji.end()) - ji.begin();
            int amax2 = max_element(ou.begin(), ou.end()) - ou.begin();
            return n - max(tmp_max1 + ou[amax2], tmp_max2 + ji[amax1]);
        }   
    }
};

T3

给你一个 正 整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少 还有 一颗 魔法豆的袋子）魔法豆的数目 相等 。一旦魔法豆从袋子中取出，你不能将它放到任何其他的袋子中。

请你返回你需要拿出魔法豆的 最少数目。

分析：

排序，记录一下后缀和

枚举每个位置作为最终答案的结果，那么比它小的必然要全变成0，比它大的都变成这个位置的数，搞个后缀和即可

typedef long long ll;
class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        int n = beans.size();
        vector<ll> s(n + 5);
        sort(beans.begin(), beans.end());
        for(int i = n - 1; i >= 0; i -- ) {
            s[i] = s[i + 1] + beans[i];
        }
        ll res = 1e18, sum = 0;
        for(int i = 0; i < n; i ++ ) {
            res = min(res, sum + s[i + 1] * 1ll - beans[i] * 1ll * (n - 1 - i));
            sum += beans[i];
        }
        return res;
    }
};