手套

题目来源

牛客网：手套

题目描述

在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。

给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。

示例

输入

4,[0,7,1,6],[1,5,0,6]

返回

10(解释：可以左手手套取2只，右手手套取8只)

思路分析

• 理解题意，左右手颜色和下标是对应的，即left和right数组中下标相同代表的是同一种颜色
• 对于非0递增序列a1,a2…an，要想最终取值覆盖每一个种类
  n = sum(a1…an) - a1 + 1（即总数减去最小值之后加一）
• 对于左右手手套颜色都有数量的序列，想要覆盖每一种颜色，则最小数量leftsum = 左边数量和 - 左边最小值 + 1， rightsum = 右边数量和 - 右边的最小值 + 1。最终取两边和较小的一个，在另一边任取一只即可。
• 考虑有0只的情况，对于有一边手套数量为零，则该颜色的手套必须全部取，因为有0就表示这种颜色无法组成配对，而我们在取的时候是无法判断哪种是有0只的，所以必须将这种颜色的另一边全部取走，即一种颜色左边为0只则取走右边所有的，右边为0则取走左边所有的。
• 所以最终取手套的方法是：假设leftsum

代码展示

class Gloves {
public:
    int findMinimum(int n, vector<int> left, vector<int> right) {
        int RightSum=0;
        int LeftSum=0;
        int RightMin=INT_MAX;
        int LeftMin=INT_MAX;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            if(left[i]*right[i]==0)
            {
                //排除一边有0只无法组对的
                sum+=left[i]+right[i];
            }
            else
            {
                //统计不为0的只数和
                LeftSum+=left[i];
                RightSum+=right[i];
                //分别找出左右手只数最少的手套
                if(left[i]<LeftMin)
                {
                    LeftMin=left[i];
                }
                if(right[i]<RightMin)
                {
                    RightMin=right[i];
                }
            }
        }
        //前面的两个+1表示最少的颜色的取1只，后面的＋1表示在另一只手取一只
        sum+=min(LeftSum-LeftMin+1,RightSum-RightMin+1)+1;
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36