题解 | #手套#

首先为了防止选到的手套是无法匹配的（另一边是0），那么就索性假设已经全都选到了他们。在此基础上，再去选择能够匹配的手套。

class Gloves {
public:
    int findMinimum(int n, vector<int> left, vector<int> right) {
        // 找出必须拿到的手套（另一边是0）
        int cnt = 0;
        for (int i=0; i<n; i++) {
            if (left[i] == 0 || right[i] == 0) cnt += left[i] + right[i];
        }

        // 如果 左 边保证所有可能配对的手套都拿到最少一只
        int res_l = 0, minv = 50;
        for (int i=0; i<n; i++) {
            if (left[i] != 0 && right[i] != 0) {
                res_l += left[i];
                minv = min(minv, left[i]);
            }
        }
        res_l -= minv - 1;

        // 如果 右 边保证所有可能配对的手套都拿到最少一只
        int res_r = 0;
        minv = 50;
        for (int i=0; i<n; i++) {
            if (left[i] != 0 && right[i] != 0) {
                res_r += right[i];
                minv = min(minv, right[i]);
            }
        }
        res_r -= minv - 1;
        // 找出最小的所有手套都拿一只的那边，另一边只需要随便拿一只可配对的就行
        return min(res_l, res_r) + cnt + 1;
    }
};