【整数二分】难题选讲

对应洛谷题单里面【整数二分】几道同学们不太好理解的题目，写个解析
A-1数对题目链接
实际上本题方法很多，我先说个好做的办法
我们可以用map标记所有数的个数，枚举数字A[i],在map里面查找C-A[i]数字的个数，统计答案即可，这种方法很简单，而且map查询也是O(logN)

 for(int i=1;i<=n;i++){
        read(a[i]);
        s[a[i]]++;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
      ans=ans+s[a[i]-m];
    }

重点讲下本题如何二分来做？？？
我们对所有的数值排序后，每次去二分查找到A[i]+C出现的最小下标以及最大下标，做差即可。排序后一定是AAAABBBBBCCCCCDDDD这样

P1678 烦恼的高考志愿
因为本题估分可能超过录取线，也可能低于录取线，总之差的绝对值就是不满意度，为了计算某个估分的不满意度，实际上我们需要两个分数，
存在录取分数[i]小于等于估分且估分小于录取分数[i+1],毕竟要计算估分少了或大了两种情况的不满意度，取最小值。

我们对录取分数线排序一下，为了更好地明确范围，我们把原本录取分数数组两端新增两个值，一个极小值-1e9，一个极大值1e9，然后二分查找录取分数里面小于等于当前估分且最接近当前估分的录取分数的位置。查找到以后计算答案即可。注意本题答案最终超过int范围

如果本题只有70分，说明左端点没考虑好。

#include<bits/stdc++.h>
using namespace std;
int G[100005];//估分 
int F[100005]; //录取分 
int main(){
	int n,m;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++){
		scanf("%d",&F[i]);
	}
	sort(F+1,F+1+m);
	F[m+1]=1e9;
	F[0]=-1e9;
	long long int sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&G[i]);
		int L=0,R=m+1;//二分左边录取分最接近估分的位置
		//那么估分一定在F[L]~F[L+1]里面求得最小不满意 
		while(L<R){
			int mid=(L+R+1)/2;
			if(F[mid]<G[i]){
				L=mid;
			}
			else{
				R=mid-1;
			}
		}
		sum=sum+min(abs(G[i]-F[L]),abs(F[L+1]-G[i]));
	}
	printf("%lld",sum);
	return 0;
}

P8160 [JOI 2022 Final] 星际蛋糕 (Intercastellar)
本题呢，先按题目说的把偶数都拆了吧，其实很好写，直接写个while循环就能搞定。假如是一开始$i$位置的数是$A[i]$ 那么直接对$A[i]$操作就好了，$A[i]$表示从左到右的第$i$段位置最终的数字。既然涉及到一段一段数字的拆分，很显然我们能计算出某段数字的起点以及终点，这个怎么计算呢？其实就是从左到右的一个过程，每次拆完数字以后，计算出这一段数字有多少个，我们当前的总长度+1就是本段数字的起点位置，当前总长度+当前段的长度就是本段数字的终点，因为前面也有很多段数字。

计算$sum[i]$表示前$i$段数字的终点位置，最终我们对于每个查询的$Xj$直接二分找到严格小于$Xj$且最大的位置$L$，那么第$Xj$位置的数一定处于第$L+1$段里面

#include<bits/stdc++.h>
using namespace std;
long long int pos[200005];
long long int sum[200005];
long long int w;
int A[200005];
bool check(int x){
	return sum[x]<w;
}
int main(){
	int n,q;
	scanf("%d",&n);
	int len=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&A[i]);
		int cnt=1;
		while(A[i]%2==0){
			A[i]=A[i]/2;
			cnt=cnt*2;
		}
		pos[i]=len+1;//第i种数的起点
		len=len+cnt;//终点 
		sum[i]=sum[i-1]+cnt;//sum[i]表示前i种数结束的位置 
	}
	scanf("%d",&q);
	while(q--){
	   scanf("%lld",&w);
	   int L=0,R=n;	
		while(L<R){
			int mid=(L+R+1)/2;
			if(check(mid)){
				L=mid;
			}
			else{
				R=mid-1;
			}
		}
		//二分找到严格小于w的位置，那么w必定处于L+1的位置里面 
		printf("%d\n",A[L+1]);
	}
	return 0;
}