题解 | #手套#

手套

手套

/*
2022-09-29 15:49:24
要想能够让左右手套至少有一副配对
我们可以先把左手手套每种都至少拿一只，然后再随便拿一只右手手套就可以成功配对
问题就是如何保证每种手套都能拿一种。
以【3 7 2 3 5】为例
拿5种？肯定不行的，有可能都是同一个颜色
拿7种？不行，有可能都是同一个颜色
8？也不行
。。。
全部拿走？不合适了
全部拿走再减去最少的，这样有可能就缺了最少的一种颜色，因此再+1
这个手套数量最少不能是0，如果是0会产生10个手套，取11次的bug

如果某个颜色没有手套，就必须得把该颜色对应的另一边手套累加起来。

先计算出左手和右手手套的总数，然后减去各自的最少的数再加一
这样就可以保证取出的手套至少每种都有一只
计算总数的时候，要找出手套数量最少的那个颜色
比较两者较小的那个数，决定先取左手还是先取右手
最后再加上另一种手套的一只就行
*/
class Gloves {
public:
    int findMinimum(int n, vector<int> left, vector<int> right) {
        int leftSum = 0, leftMin = INT_MAX;
        int rightSum = 0, rightMin = INT_MAX;
        int ret = 0;
        for(int i = 0; i < n; ++i)
        {
            if(left[i] == 0 || right[i] == 0)
            {
                ret += left[i] + right[i];
            }
            else
            {
                // 更新数量最少的手套
                leftMin = min(leftMin, left[i]);
                rightMin = min(rightMin, right[i]);
                leftSum += left[i];
                rightSum += right[i];
            }
        }
        // 遍历结束，判断左边的最少还是右边最少 加入左手最少的，就再从右手随便取一只
        ret += min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1;
        return ret;
    }
};