你绝对不知道的二分新使用
2020.3.8
刚刚复盘前两天做的LeetCode475，一个关于二分的题。又发现一点。
当我们在找一个num中存在的数字的时候，模板是没有问题的。但是需要一个num中离key最近的一个数字时，可能会出现问题。
当key在最大与最小值之间时，left和right刚刚好一个右一个左连续的。
但是当key小于最小值时，最后一次循环right-1，会让left：0，right：-1；
同理当key大于最大值时，最后一次循环left+1，会让left：size-1，right：size；
只需要打一个补丁就好了
if(left==heatersSize) low--;
if(right==-1) high++;
dis=my_min(my_abs(houses[h]-heaters[low]),my_abs(houses[h]-heaters[high]));
2020.3.6
今天群里分享了二分，恰好看到一个公众号对二分的理解，感觉这一波应该是圆满了。
首先我们先明白二分的大致模板：
left=0,right=num.length()-1;
while(left<=right){
mid=left+(right-left)/2;
if(num[mid]==key){}
else if(num[mid]<key) {
left=mid+1;
}else if(num[mid]>key){
right=mid-1;
}
}
今天要解决的问题就是 +-1 和 取不取等号 的问题。
为了解决这个问题，我们重新审视一下我们的模板代码。
left=0,right=num.length()-1;
我们的区间现在是整个数组的闭区间，即一左一右两个指针必须在分区间后同样严格指向该区间两端。
···
while(left<=right)
···
当到达left==right 的时候，继续循环。
此时mid=left=right，本次循环就检测这一个数，该数本身闭区间，即[2]。
left=mid+1; / right=mid-1;
原本我们的区间是{[left, mid, right]}
mid已经检测过了，同时要严格保证闭区间，就应该相应改动区间为{[left， X]， mid，right}或者{left，mid[X，right]}
所以只需要牢记区间统一即可。在这里我在po一个其他样式的代码。
left=0,right=num.length();
while(left<right){
mid=left+(right-left)/2;
if(num[mid]==key) {}
else if(num[mid]<key) left=mid+1;
else if(num[mid]>key) right=mid;
}
if(left>=num.length()) Do
else if(num[left]==key) Do
当然，如果while里面非要写 = ，那么会漏掉一个left的比较，循环结束后要判断left越界或者是等于key，注意一下，left一直在往right跑，所以if的语句，对应right判断应该是小于0。最好不要用这种打补丁方式，po一下LeetCode中532题对比
int low=i+1,high=numsSize-1;
while(low<high){
int mid=(low+high)/2;
if(nums[mid]==(nums[i]+k)){cnt++; break;}
else if(nums[mid]<(nums[i]+k)) low=mid+1;
else if(nums[mid]>(nums[i]+k)) high=mid-1;
}
if(low<numsSize && low==high && nums[low]==(nums[i]+k)) cnt++;
}
和
int low=i+1,high=numsSize-1;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==(nums[i]+k)){cnt++; break;}
else if(nums[mid]<(nums[i]+k)) low=mid+1;
else if(nums[mid]>(nums[i]+k)) high=mid-1;
}
就离谱！
今天实验室讲了二分，然鹅！！我没起来！！！
于是，只有自己看一看，学一学二分思想。
首先，二分是有适用条件的，一般来说，答案必须是离散的点，并且我们二分的是答案。同时，二分必须要满足单调性，即假设t0是答案，那么大于/小于t0的都可以满足条件，小于/大于t0的都不满足条件。
Matrix（POJ3685）
题意：给你一个NXN的矩阵，告诉你矩阵中(i,j)点的值为 i^2 + 100000 × i + j^2 - 100000 × j + i × j，问第M小的数字是多少。
分析：其实刚刚拿到题目的时候，就想到了之前做的4 Values whose Sum is 0(POJ2785)这道题。不过两道题还是有不一样的，就本题而言，由给你的公式我们可以看出来，当我们固定j不动时，i是单调递增的，即满足单调性，我们就可以二分答案了。
但是这样还不够，这只是相当于枚举了j的值，我们还需要枚举i的值才能得到答案。怎么枚举能，肯定就是看小于 枚举答案的 数字的个数。我们可以根据每一列的单调性就可以二分了。
这就是传说中的二分套二分！！！
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll isOk(ll i,ll j){
return i*i+100000*i+j*j-100000*j+i*j;
}
bool check(ll x){
ll res=0;
for(ll j=1;j<=n;j++){
ll l=1;
ll r=n;
ll tmp=0;
while(l<=r){
ll mid=(l+r)>>1;
if(isOk(mid,j)<=x){
tmp=mid;
l=mid+1;
}else{
r=mid-1;
}
}
res+=tmp;
if(res>=m) return true;
}
return false;
}
void Solve()
{
scanf("%lld%lld",&n,&m);
ll l=-(ll)100000*n;
ll r=n*n+(ll)100000*n+n*n+n*n;
ll ans;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
printf("%lld\n",ans);
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
还有一道二分卡精度的问题Cable master(POJ1064)
题意：给你n个长度不等的线段，让你切割这些线段，使得最后有m段一样长的线段，问这m长的线段的长度是多少。
分析：其实二分还是很好想的，还是用单调的特点，假设这m段的长度为ans，当长度大于ans时，就不能达到m段；当长度小于ans时，就可以择一定能切割刀大于等于m段。
主要这道题有精度问题，题目中答案在1 meter到1 kilometer之间，输出的时候要精确到centimeter。同时还要注意一点，如果你的数值是3.457，那么
/********************************
Author: Audrey_H
Motto:talk is cheap,show me the code.
********************************/
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define lowbit(x) (x&(-x))
#define PB(x) push_back(x)
#define ll long long
#define PI acos(-1.0)
#define FILEIN freopen("in.txt","r",stdin)
#define FILEOUT freopen("out.txt","w",stdout)
#define CLR(x) memset(x,0,sizeof(x))
#define mem(a,x) memset(a,x,sizeof(a))
#define debug printf("!!");
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
const double eps = 1e-6;
const ll mod = 1e9+7;
const int maxn = 1e5+100;
const int maxe = 1e6+100;
using namespace std;
double num2[maxn];
int n,k;
bool check(double x){
int tnum=0;
for(int i=1;i<=n;i++){
tnum+=(int)(num2[i]/x);
}
if(tnum>=k) return true;
else return false;
}
void Solve()
{
scanf("%d%d",&n,&k);
double sum=0;
for(int i=1;i<=n;i++){
scanf("%lf",&num2[i]);
sum+=num2[i];
}
double l=0,r=sum;
double ans=0;
for(int i=1;i<=100;i++){
double mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid;
}else{
r=mid;
}
}
if((int)(ans*1000)%10>=5){
ans-=0.005;
}
printf("%.2f\n",ans);
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int Case=1,cases;
//scanf("%d", &Case); cases=Case;
while(Case--){
//printf("Case #%d:",cases-Case);
Solve();
}
return 0;
}
