OR57 手套

练习题入口

问题描述

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

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

测试样例：

解题分析

       解析这道题，我们可以分成两步：

第一步：怎样选取一定能保证配对一双手套

如上图，我们是不是可以把左手套全部取完，然后再在右手套中取一双，这样就能保证最少配对一双手套（反之把右手套取完）。

例如：把左手套取完 2+3+2+4 = 13

          右手套至少要有一只用来配对：1

总数：13+1=14

第二步：如何确保取出的手套是最少的

  我们可以对比左和右中的手套总数，然后分别减去其中最小的数量的手套数，最后加1

  那边算出的总数少就用哪边的。

为什么要减去数量最少的那一种手套？

     假设我们减去 left[1]位置的手套，也就是减3，然后再+1算出总数，+1的目的是想让减去那一种手套也留下一只。

      结果为 9 ，我们想要这9只的手套的数量分别为 2  1  2  4，此时就不能按照我们心中所想了，会有多种排列组合 例如 0  3  2  4   left[0]种类的手套直接没有！！！

   

     所以我们要减去数量最小的手套，我们再取的时候就只会有一种组合

第三步：解决某一种手套为0的情况

   当有一种手套为0时，我们再计算的结果就会超过手套总数，所以我们再算取出手套数时要先把为0放一边。

 这时，最下值也要变，从 0 变为 1

最后我们定义一个sum 把数量为0的手套的配对手套加起来，再与第二步算出的手套数相加

总步骤：      

代码实现

import java.util.*;
public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        // write code here
        int sumLeft = 0;
        int sumRight = 0;
        int minLeft = Integer.MAX_VALUE;
        int minRight = Integer.MAX_VALUE;
        int sum = 0;
        for(int i = 0;i < n;i++){
            if(left[i]*right[i] == 0){
                sum += left[i] + right[i];
            }else{
                sumLeft += left[i];
                sumRight += right[i];
                if(minLeft > left[i]){
                    minLeft = left[i];
                }
                if(minRight > right[i]){
                    minRight = right[i];
                }
            }
        }
        return Math.min(sumLeft - minLeft+1,sumRight - minRight +1)+1+sum;
    }
}