首页 > 试题广场 >

手套

[编程题]手套

热度指数：5779 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

测试样例：

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

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

算法知识视频讲解

Java

two倩

1、最小的手套个数：就是下面两种数字的最小值

左手保证全部颜色都有 +右手保证有一个可以被配套的颜色

右手保证全部颜色都有 +左手保证有一个可以被配套的颜色

2、注意0

情况一：都不包含0

[2,9,3]和[1,2,7]

//如果是左手保证全部颜色都有，那么就是9+3+1=13，也就是2+9+3-最小值2+1=13，右手保证有一个可以被配套的颜色就是1，结果14

//如果是右手保证全部颜色都有，那么就是1+2+7-1 +1=10，左手保证有一个可以被配套的颜色就是1，结果11

最终值11

情况二：有一个包含0

[0,9,3]和[1,2,7]

//如果是左手保证全部颜色都有，那么就是9+3-3+1=10，右手保证有一个可以被配套的颜色就是2,因为第一个颜色左边是0个手套，那么右手就必须拿上全部这个颜色的手套，然后保证拿一个可以配对的颜色结果12

//如果是右手保证全部颜色都有，那么就是拿上左手没有的颜色1个，然后保证在二三颜色中拿到全部颜色，2+7-2+1=8， 8+1=9，左手保证有一个可以被配套的颜色就是1，结果10

最终值10

情况三：左右都包含0

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

//如果是左手保证全部颜色都有，因为第三个颜色右手没有，那么就要保证拿到所有这个颜色的手套1个，然后第二个,第四个颜色中保证全部有，那就是7+6-6+1=8个，总共9个

右手保证有一个可以被配套的颜色就是2,因为第一个颜色左边是0个手套，那么右手就必须拿上全部这个颜色的手套，然后保证拿一个可以配对的颜色 2个，结果11

//如果是右手保证全部颜色都有，因为第一个颜色左手没有，带上这个元素的手套1个，第2、4个颜色保证都有，5+6-5+1=7个，总共8个

左手保证有一个可以匹配的元素，第三个颜色要拿，然后带一个其他颜色的手套 2个

总共10个

最终值10个

也就是如果左手拿全部元素或者保证有一个可以匹配的元素，右手right[i]==0,那么这个颜色对应的元素是一定要拿的，右手也一样；如果是取有一个可以匹配的元素，在以上的计数上+1即可；如果左手拿全部元素，那么就要在其他right[i]!=0的颜色中，保证可以拿到全部颜色的个数，这个个数就是元素之和-最小值+1

对于右手也一样，然后比较，得到两种情况下的最小值

import java.util.*;

public class Gloves {
public int findMinimum(int n, int[] left, int[] right) {
// write code here

int leftmin=27;//记录最小值
//题目说明总数<=26
int rightmin=27;
int numsleft=0;//左手拿全部颜***r /> int numsright=0;//右手拿全部颜***r /> int lefts=0;
int rights=0;//保证右手保证一个颜***r /> for(int i=0;i<n;i++){
if(left[i]==0&&right[i]==0){
continue;
}
else if(left[i]==0&&right[i]!=0){
//无论右手拿全部颜色的手套还是至少拿一种，右手一定要拿到全部这个颜***r /> numsright+=right[i];
rights+=right[i];
}else if(left[i]!=0&&right[i]==0){无论左手拿全部颜色的手套还是至少拿一种，左手一定要拿到全部这个颜色
numsleft+=left[i];
lefts+=left[i];
}else{
//左手计算全部元素
numsleft+=left[i];
leftmin=Math.min(leftmin,left[i]);

//右手计算
numsright+=right[i];
rightmin=Math.min(rightmin,right[i]);
}
}
//左手拿全部+右手拿保证一个
return Math.min( rights+1 + numsleft-leftmin+1,lefts+1+ numsright-rightmin+1);

}
}

发表于 2022-08-21 23:49:12 回复(0)

Java

牛客400708394号

    public int findMinimum(int n, int[] left, int[] right) {
        int leftSum = 0;
        int rightSum = 0;
        int sum = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if(left[i]*right[i] == 0){
                sum += left[i] + right[i];
            }else {
                leftSum += left[i];
                rightSum += right[i];
                if(leftMin > left[i]){
                    leftMin = left[i];
                }
                if(rightMin > right[i]){
                    rightMin = right[i];
                }
            }
        }
        return Math.min(leftSum - leftMin + 1,rightSum - rightMin +1) + sum + 1;
    }

发表于 2022-07-19 17:41:56 回复(0)

Java

来学习的小张

import java.util.*;

public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        int sum = 0;
        int leftSum = 0;
        int rightSum = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        for(int i = 0;i < n;i++){
            if(left[i] * right[i] == 0){
                sum = sum + left[i] + right[i];
            }else{
                leftSum += left[i];
                if(leftMin > left[i]){
                    leftMin = left[i];
                }
                rightSum += right[i];
                if(rightMin > right[i]){
                    rightMin = right[i];
                }
            }
        }
        return sum + Math.min(leftSum - leftMin +1,rightSum - rightMin + 1) + 1;
    }
}

发表于 2022-04-05 21:25:53 回复(0)

Java

Holiday_12138

反过来想就是最多能选出多少个不配对的手套

当一边存在0时，另一边自然可以全部选择而保证不会配对。

两种选择方案，1、左边至少覆盖所有颜色（对应右边为0时的颜色，要都算在内），右边除了对应左边为0的颜色中至少选择一个；

2、右边至少覆盖所有颜色（对应左边为0时的颜色，要都算在内），左边除了对应右边为0的颜色中至少选择一个。

从两种中选择较少的一个。

import java.util.*;

public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        int lmax1,rmax1,lmax2,rmax2;//lmax1，rmaxl，表示某个颜色有一边是0个时，另一边的所有相应颜色手套都要选择。
        lmax1=rmax1=lmax2=rmax2=0;
        for(int i=0;i<n;i++){
            if(left[i]==0){
                rmax1+=right[i];
                right[i]=0;
            }
            if(right[i]==0){
                lmax1+=left[i];
                left[i]=0;
            }
        }
        Arrays.sort(left);
        Arrays.sort(right);
        int i=n-1;
        while(i>=0&&left[i]>0){
            lmax2+=left[i];//去掉0的情况后，其余的手套按照从大到小除去最小的一个全部相加再加1.
            i--;
        }
        lmax2-=(left[i+1]-1);
        i=n-1;
        while(i>=0&&right[i]>0){
            rmax2+=right[i];
            i--;
        }
        rmax2-=(right[i+1]-1);
        int ans1=rmax2+lmax1+rmax1+1;
        int ans2=lmax2+lmax1+rmax1+1;
        int res=ans1>ans2?ans2:ans1;
        return res;
    }
}

编辑于 2017-03-01 15:40:36 回复(0)

Java

阿华

package shoutao;

import java.util.*;

public class Gloves {
 
 public static void sort(ArrayList<Integer> list,int begin,int end){
  
  if(begin>=end){return ;}
  
  int i = begin;
  int j = end;
  int temp;
  int mark =end;
  
  while(i<j){
   while(i<j&&list.get(begin)<=list.get(j)){
    
    j--;
   }
   while(i<j&&list.get(begin)>=list.get(i)){
    
    i++;
   }
   if(i<j){
    
    temp = list.get(i);
    list.set(i,list.get(j));
    list.set(j, temp);
   }
   else if(i==j){
    temp = list.get(i);
    list.set(i, list.get(begin));
    list.set(begin, temp); 
    
    mark =i;
   }
   }
  
  sort(list,begin,mark-1);
  sort(list,mark+1,end);
  
  
  
 }
 
 
    public int findMinimum(int n, int[] left, int[] right) {
        // write code here
     ArrayList<Integer> arrL = new ArrayList<Integer>();
     
     int cantMatchLeft = 0;
     
     int cantMatchRight =0;
     
     ArrayList<Integer> arrR = new ArrayList<Integer>();
     
     
     for(int i=0;i<n;i++){
      
      if(left[i]==0){cantMatchRight+= right[i];}
      
      if(right[i]==0){cantMatchLeft+=left[i];}
      
      if(left[i]!=0&&right[i]!=0){
       
       arrL.add(left[i]);
       arrR.add(right[i]); 
      } 
     }
     
     sort(arrL,0,arrL.size()-1);
     sort(arrR,0,arrR.size()-1);
     
     int numberL = 1;
     int numberR =1;
     
     for(int i=1;i<arrL.size();i++){
      
      numberL += arrL.get(i);
     }
     for(int i=1; i<arrR.size();i++){
      
      numberR += arrR.get(i);
     }
     
     // 2种选择策略
     int res1 = (cantMatchLeft+cantMatchRight)+(numberR)+1;
     
     int res2 = (cantMatchLeft+cantMatchRight)+(numberL)+1;
     
     return  res1<res2 ?res1 :res2;
     
     
     
     
    }

发表于 2016-07-11 10:31:08 回复(0)