(二分搜索——最大化最小值)CF-C. Block Towers_综合

传送门： CF-C. Block Towers

Students in a class are making towers of blocks. Each student makes a (non-zero) tower by stacking pieces lengthwise on top of each other. n of the students use pieces made of two blocks and m of the students use pieces made of three blocks.

The students don’t want to use too many blocks, but they also want to be unique, so no two students’ towers may contain the same number of blocks. Find the minimum height necessary for the tallest of the students' towers.

Input

The first line of the input contains two space-separated integers n and m (0?≤?n,?m?≤?1?000?000, n?+?m?>?0) — the number of students using two-block pieces and the number of students using three-block pieces, respectively.

Output

Print a single integer, denoting the minimum possible height of the tallest tower.

Note

In the first case, the student using two-block pieces can make a tower of height 4, and the students using three-block pieces can make towers of height 3, 6, and 9 blocks. The tallest tower has a height of 9 blocks.

In the second case, the students can make towers of heights 2, 4, and 8 with two-block pieces and towers of heights 3 and 6 with three-block pieces, for a maximum height of 8 blocks.

题解：满足二分查找的条件----1.单调性的问题；2.判断比较简单。

#include<iostream>
using namespace std;int n,m;
bool check(int x)
{int num1=x/2;int num2=x/3;int num3=x/6;if(num1<n) return false;if(num2<m) return false;if(min(num3,num1-n)<m-(num2-num3)) return false;//本题关键：利用贪心的思想，把2和3公倍数，尽可能的都给3，这样可能确保满足条件的值最小 return true;
}int main()
{scanf("%d%d",&n,&m);int l=0,r=1e7,ans=0;while(l<=r){int mid=(l+r)/2;if(check(mid))	ans=mid,r=mid-1;else l=mid+1;}printf("%d\n",ans);return 0;
}

2018/6/6再次回头看这题，发现check()里的并不好理解，所以有重写了一个

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;bool C(int x){int num1=x/2,num2=x/3,num3=x/6;return num1>=n&&num2>=m&&(num1+num2-num3)>=n+m;
}void solve(){int lb=0,ub=1e7;while(ub-lb>1){int mid=(lb+ub)/2;if(C(mid)) ub=mid;else lb=mid;}printf("%d\n",ub);
}int main()
{scanf("%d%d",&n,&m);solve();return 0;
}