在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。
给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。
4,[0,7,1,6],[1,5,0,6]
返回：10(解释：可以左手手套取2只，右手手套取8只)
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
int s=0,L=0,R=0,min_l=INT_MAX,min_r=INT_MAX;
for(int i=0;i<n;i++)
{
if(left[i]==0 || right[i]==0)
s += (left[i] + right[i]);
else{
L += left[i];
R += right[i];
min_l = min(min_l, left[i]);
min_r = min(min_r, right[i]); } } return s + min(L-min_l+1, R-min_r+1) + 1;
}
};
import java.util.*;
public class Gloves {
public int findMinimum(int n, int[] left, int[] right) {
int sum=0;
int leftMin = Integer.MAX_VALUE;
int rightMin = Integer.MAX_VALUE;
int leftSum = 0;//辅助变量
int rightSum = 0;//辅助变量
for(int i=0;i<n;i++){
if(left[i]==0&&right[i]!=0){//只要此颜色，左手没有，右手有的手套，右手个数计入sum
sum+=right[i];
continue;
}
if(left[i]!=0&&right[i]==0){//只要此颜色，右手没有，左手有的手套，左手个数计入sum
sum+=left[i];
continue;
}
if(left[i]==0&&right[i]==0)
continue;
if(leftMin>left[i])
leftMin=left[i];
if(rightMin>right[i])
rightMin=right[i];
leftSum += left[i];
rightSum += right[i];
}
leftSum = leftSum-leftMin;
rightSum = rightSum-rightMin;
int x = leftSum<rightSum?leftSum:rightSum;//如果左手手套比较少，则可以右手手套取2个，左手尽可能配对。
return sum+x+2;
}
}
/*
* *有两种方式：
* 1：把左手套全部拿出来，右手套选出一个，即可配对
* 2：把右手套全部拿出来，左手套选出一个，即可配对
* 但是这两种方法缺乏一点考虑，1中从右手套中选出配左手套，有一种情况
* 左手套中可能有一种颜色为0，而右手套却有这种颜色，这时如果选择这个右手套
* 就不可以配对，所以总数需要1+这类右手套的个数才可成功配对，此外还有一点
* 需要考虑，就是只需要配对一个即成功，所以把左右手套都有的颜色中左手套个数
* 最少的手套数变为1，因为多了也是冗余。2中类似。
* 程序中的max = max - min + 2可以理解为
* max = max -(min - 1) + 1
*/
import java.util.*;
public class Gloves {
public int findMinimum(int n, int[] left, int[] right) {
int max1 = 0, max2 = 0, min1 = 27,min2 = 27;
for(int i = 0; i < n; i++){
if(left[i] == 0 && right[i] != 0){
max1 += right[i];
max2 += right[i];
}
if(left[i] != 0 && right[i] == 0){
max2 += left[i];
max1 += left[i];
}
if(left[i] != 0 && right[i] != 0){
max1 += left[i];
max2 += right[i];
if(left[i] < min1)
min1 = left[i];
if(right[i] < min2)
min2 = right[i];
}
}
max1 = max1 - min1 + 2;
max2 = max2 - min2 + 2;
return (max1 < max2) ? max1 : max2;
}
}
import java.util.*;
public class Gloves {
public int findMinimum(int n, int[] left, int[] right) {
int sum = 0;
List<Integer> leftList = new ArrayList<Integer>();
List<Integer> rightList = new ArrayList<Integer>();
for (int i = 0; i < n; i++) {
if ((left[i] == 0 && right[i] != 0) || (left[i] != 0 && right[i] == 0)) {
sum += left[i] + right[i];
} else if (left[i] != 0 && right[i] != 0){
leftList.add(left[i]);
rightList.add(right[i]);
}
}
Collections.sort(leftList);
Collections.sort(rightList);
int sum1 = 0, sum2 = 0;
for (int i = leftList.size() - 1; i > 0; i--) {
sum1 += leftList.get(i);
}
for (int i = rightList.size() - 1; i > 0; i--) {
sum2 += rightList.get(i);
}
return Math.min(sum1, sum2) + 2 + sum;
}
}
//思路：假设有一序列 a1<a2<a3<a4<...<an，选出多少个能够保证覆盖n种颜色？
//答案是 sum(a1...an)-a1+1，类似鸽巢原理
//所以先求出左手套和右手套哪边能够覆盖n种颜色，而且还能少拿手套？
//答案是 min(leftSum-leftMin+1,rightSum-rightMin+1)，这个确定以后，
//只需要在另一边随便选择一个就能够保证至少有一种颜色匹配了
//另外要注意某种颜色手套数为0的情况
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
// write code here
int sum=0;
int leftSum=0,rightSum=0;
int leftMin=30,rightMin=30;
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];
leftMin = min(leftMin,left[i]);
rightMin = min(rightMin,right[i]);
}
}
return sum + min(leftSum-leftMin+1,rightSum-rightMin+1) + 1;
}
};
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
// write code here
int left_sum = 0, left_min = INT_MAX;
int right_sum = 0, right_min = INT_MAX;
int sum = 0;
for(int i = 0; i < n; i++)
{
// 左边或者右边没有的时候需要全部拿走(最差结果)
if(left[i] * right[i] == 0)
{
sum += left[i] + right[i];
}
// 找到左边和右边分别最少的颜色的数量并计算总和
else{
left_sum += left[i];
right_sum += right[i];
left_min = min(left[i], left_min);
right_min = min(right[i], right_min);
}
}
// 找到左边和右边中较小的值，在另一边直接拿一个就可以保证题意
return sum +min(left_sum - left_min + 1, right_sum - right_min + 1) + 1;
}
}; 待定
这道题的关键点如下
所以本题的解题思路就是，首先拿取左面或右面的手套，使拿取的数目覆盖全部颜色，然后相应的另一半手套只需挑出一即可
以拿出左面为例，有5只颜色不同的左手套
由于无法分辨颜色，所以拿取的时候，如果数目太小，就可能无法覆盖全部手套。比如拿取15只手套，白色的可能就没有覆盖到。所以一旦左面取了15只，就白色的没取，而右面取了一只，恰好就是白色，就导致无法匹配
而如果全取，就不能保证题目“至少”要求了
所以应该这样取：手套数目=总手套数目-最少的颜色的手套+1 。这样取一定可以保证所有手套全部覆盖到
如果一个手套中出现了0，那么将导致对应的手套无法被匹配到，所以这种情况下要把0对应的手套（不管是左还是右都取出来），才能保证不被这种糟糕的情况给破坏掉
最后应该是取左面还是右面的呢？其实这不重要，左面小就取左面的，右面小就取右面的，最后只需在对方手套中取一只即可。
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right)
{
int left_sum=0;
int right_sum=0;//分别计算左面手套和右面手套的综合
int left_min=INT_MAX;
int right_min=INT_MAX;//分别用来保存左面或者右面的最小手套数目
int sum_zero=0;//统计一方出现手套为0的手套数目
for(int i=0;i<n;i++)//有n种颜色的手套
{
if(left[i] * right[i] == 0)//只要一方有0，统计
{
sum_zero+=left[i]+right[i];
}
else
{
left_sum+=left[i];//统计左手套的数目
left_min=min(left_min,left[i]);//左手套中颜色最少的
right_sum+=right[i];//同上
right_min=min(right_min,right[i]);
}
}
//谁少取谁
int get=min(left_sum-left_min+1,right_sum-right_min+1);
return sum_zero+get+1;//最后返回时只要任取对面的1个手套以及取完所有为0的情况和一方手套
}
}; 
一道数学问题，考虑最坏情况下的最小问题。思路如下：
1.首先把左右中所有有一只为0的数量算进来，因为一旦拿到这类手套你是无论如何都无法配成一双的。这类手套在最坏情况下必须考虑到；
2.将两个数组中符合条件1的数值成对去除，剩下的看和。由于找最少，因此只要确保剩余数量最少的那一组每种类型都拿到就可以了，那样从另一组中随便拿一只就肯定会拿到。
3.剩余数量和最少的那组排序，除了最少的其他每组都是全部拿走，这样就可以保证只要这一组再拿一只，那么所有种类手套可以都拿到。结果直接+2(即本组数量最少的那类和另一组任意一只)即为所有。
参考代码如下：
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
int MIN = 0, lsum = 0, rsum = 0;
vector<int> tlef, trig;
for (int i = 0; i < n; i++)
{
if (left[i] == 0 || right[i] == 0)
{
MIN += right[i] + left[i];
continue;
}
lsum += left[i], tlef.push_back(left[i]);
rsum += right[i], trig.push_back(right[i]);
}
if (lsum < rsum)
{
sort(tlef.begin(), tlef.end());
for (int i = tlef.size() - 1; i > 0; i--) MIN += tlef[i];
}
else
{
sort(trig.begin(), trig.end());
for (int i = trig.size() - 1; i > 0; i--) MIN += trig[i];
}
return MIN + 2;
}
};
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;
}
}
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 sum = 0;
//遍历每一种颜色的左右手套序列
for(int i = 0; i < n; ++i){
//对于有0存在的颜色手套，累加
if(left[i]*right[i] == 0){
sum += left[i] + right[i];
}
//对于左右手都有的颜色手套，执行累加-最小值+1
//找到最小值和总数
else{
leftsum += left[i];
rightsum += right[i];
leftmin = min(leftmin, left[i]);
rightmin = min(rightmin, right[i]);
}
}
//结果为有左右都有数量的手套序列的结果+有0存在的手套数+最后再加一肯定就能保证了
return sum + min(leftsum - leftmin + 1, rightsum - rightmin + 1) + 1;
}
}; 
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
// write code here
int min = 0, lmin = 0, rmin = 0;
int lm = 26, rm =26;
for (int i = 0; i < n; i++)
{
if (left[i] == 0 || right[i] == 0)
{
min += left[i];
min += right[i];
}
else
{
lmin += left[i];
rmin += right[i];
if (left[i] < lm)
lm = left[i];
if (right[i] < rm)
rm = right[i];
}
}
min += lmin > rmin ? (rmin - rm) : (lmin - lm);
return min + 2;
}
}; 
import java.util.*;
public class Gloves {
public int findMinimum(int n, int[] left, int[] right) {
// write code here
int max1 = 0,max2 = 0;
int min1 = 27,min2 = 27;
int i;
for(i=0;i<n;i++){
if(left[i] == 0){
max1 = max1+right[i];
}
else{
max1 = max1+left[i];
}
if(right[i] == 0){
max2 = max2+left[i];
}
else{
max2 = max2+right[i];
}
if(left[i]!=0 && right[i]!=0 && left[i]<min1){
min1 = left[i];
}
if(right[i]!=0 && left[i]!=0 && right[i]<min2){
min2 = right[i];
}
}
max1 = max1-min1+2;
max2 = max2-min2+2;
return (max1<max2)?max1:max2;
}
}
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
// write code here
int sum=0;
int sum_l=0,sum_r=0;
int min_l=INT_MAX,min_r=INT_MAX;
for(int i=0;i<n;i++)
{
if(left[i]*right[i]==0)
{
sum=sum+left[i]+right[i];
}
else
{
sum_l+=left[i];
min_l = left[i]>min_l?min_l:left[i];
sum_r+=right[i];
min_r = right[i]>min_r?min_r:right[i];
}
}
return sum+min(sum_l-min_l+1,sum_r-min_r+1)+1;//1是随便在另一边取一个
}
};
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
|
importjava.util.*;
publicclassGloves {
publicintfindMinimum(intn, int[] left, int[] right) {
intleftNum = findAtleast(n, left, right);
intrightNum = findAtleast(n, right, left);
intresult = leftNum > rightNum ? rightNum :
leftNum;
returnresult;
}
privatestaticintfindAtleast(intn, int[] a, int[] b) {
intleast = 0;
intmax = 0;
inttemp = 0;
for(inti = 0; i < n; i++) {
temp = 0;
if(b[i] == 0) {
least += a[i];
} else{
if(a[i] != 0) {
for(intj = 0; j < n; j++) {
if(j != i) {
temp += b[j];
}
}
if(max < temp) {
max = temp;
}
}
}
}
least++;
max = max + least + 1;
returnmax;
}
}
以左边为基准，求出可行的至少取出一种颜色手套的只数a（本例中为2，因为right[2]=0），之后再计算取出各种颜色右边至少要取出的手套数量，取出最大b即可。
最后返回a+b；再以右边为基准同理求出a'+b'，取最小即可。
|
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
int leftsum=0; //左手套的总数
int rightsum=0;//右手套的总数
int leftmin=30; //左手套中颜色数量最少的
int rightmin=30; //右手套中颜色数量最少的
int sum_zero=0;
for(size_t i=0;i<n;i++)
{
if(left[i]*right[i]==0) //当这个其中某一个手套的个数为0，那么这个就都拿了
{
sum_zero+=left[i]+right[i];
}
else //其他情况
{
leftsum+=left[i]; //求左手套之和
rightsum+=right[i]; //求右手套之和
leftmin=min(leftmin,left[i]); //不断迭代leftmin保存左手套最小
rightmin=min(rightmin,right[i]); //不断迭代rightmin保存右手套最小
}
}
//中间的min(leftsum-leftmin+1,rightsum-rightmin+1) 是最少左手套或者右手套可拿的数量 sum_zero是必须拿的因为不会构成颜色相同的一对手套 然后在左右两个随便取一个就构成一双颜色相同的手套
return sum_zero+min(leftsum-leftmin+1,rightsum-rightmin+1)+1;
}
}; 
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right) {
// write code here
//本题没有思路，是看答案才写出来的
//如果手套的颜色不为0，那么只需要取出左边的全部的颜色，然后在从右边随便取一直，就能找到配对的颜色，同理从右边取出全部的颜色也是一样的
//想要取出左手的全部颜色的手套，就需要将不为0的颜色全部加起来(这里的不为0，如果右手的该颜色为0，则左手的这个颜色不需要加)，然后减去最小的一个，在加1
//如果有一种颜色左边的为0，右边的不为0，就需要将不为0 的全部的取出，同理右边的有一种颜色的手套为0，也需要将左边的该颜色不为0的全部取出
int sum = 0;
int left_sum = 0,left_min = INT_MAX;
int right_sum = 0,right_min = INT_MAX;
for(int i = 0;i < left.size();i++)
{
//说明左右手中有一个为0，则将该颜色全部的手套加起来
if(left[i] * right[i] == 0)
{
sum += left[i] +right[i];
}
//对于左右手都有的颜色手套，执行累加-最小值+1
//找到最小值和总数
else
{
left_sum += left[i];
right_sum += right[i];
//找到最小的值
left_min = std::min(left_min,left[i]);
right_min = std::min(right_min,right[i]);
}
}
//判断是取左手的全部颜色然后取一个右手的，还是取右手的全部的颜色然后取一个左手，这里找最小的数量，sum是有一方为0的，是都要取的
return sum + std::min(left_sum - left_min + 1,right_sum - right_min + 1) + 1;
}
}; class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right)
{
// write code here
int left_sum=0,left_min=INT_MAX;
int right_sum=0,right_min=INT_MAX;
int sum=0;
for(int i=0;i<n;i++)
{
if(left[i]==0 || right[i]==0)
sum+=left[i]+right[i];
else
{
left_sum+=left[i];
left_min=left_min<left[i] ? left_min : left[i];
right_sum+=right[i];
right_min=right_min<right[i] ? right_min : right[i];
}
}
return sum+ min(left_sum-left_min+1,right_sum-right_min+1)+1;
}
}; 
class Gloves {
public:
int findMinimum(int n, vector<int> left, vector<int> right)
{
int left_sum = 0, left_min = INT_MAX;
int right_sum = 0, right_min = INT_MAX;
int sum = 0;
//遍历每一种颜色的左右手套序列
for (int i = 0; i < n; i++)
{
//对于有0存在的颜色手套，累加
if (left[i]*right[i] == 0)
sum += left[i] + right[i];
//对于左右手都有的颜色手套，执行累加-最小值+1
//找到最小值和总数
else
{
left_sum += left[i];
right_sum += right[i];
left_min = min(left_min, left[i]);
right_min = min(right_min, right[i]);
}
}
return sum + min(left_sum - left_min + 1, right_sum - right_min + 1) + 1;
}
}; 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
