题解 | 手套

手套

https://www.nowcoder.com/practice/365d5722fff640a0b6684391153e58d8

解题思路

这是一个贪心算法问题。需要找到能保证配对成功的最少手套数量，需要考虑单边缺失和双边都有的情况。

关键点：

区分单边缺失和双边都有的情况
记录每边手套的总数和最小值
贪心选择较少的一边
考虑配对成功的必要条件

算法步骤：

处理单边缺失的手套
统计双边都有时的手套数量
计算最优选择策略
确保能够配对成功

代码

cpp
java
python

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;
    }
};

public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        int leftSum = 0, leftMin = Integer.MAX_VALUE;
        int rightSum = 0, rightMin = Integer.MAX_VALUE;
        int ret = 0;
        
        // 遍历所有颜色的手套
        for(int i = 0; i < n; i++) {
            if(left[i] == 0 || right[i] == 0) {
                // 单边缺失的情况，必须全部拿走
                ret += left[i] + right[i];
            } else {
                // 双边都有的情况，更新总数和最小值
                leftMin = Math.min(leftMin, left[i]);
                rightMin = Math.min(rightMin, right[i]);
                leftSum += left[i];
                rightSum += right[i];
            }
        }
        
        // 选择较少的一边，并确保能配对成功
        ret += Math.min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1;
        return ret;
    }
}

# -*- coding:utf-8 -*-
class Gloves:
    def findMinimum(self, n, left, right):
        leftSum, leftMin = 0, float('inf')
        rightSum, rightMin = 0, float('inf')
        ret = 0
        
        # 遍历所有颜色的手套
        for i in range(n):
            if left[i] == 0 or 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