二分法模板

算法介绍

二分法是一个非常高效的算法，它常常用于计算机的查找过程中。

二分答案

//二分答案 
while(left <= right)
{
    int mid = (left + right) / 2;
    if(judge(mid))
    {
        left = mid + 1;
        ans = max(ans, mid);//mid是答案，但是不一定是最大答案，寻找右边区间时，需要有一个ans记录答案
    }
    else
        right = mid - 1;
}
printf("%d", ans);

P2390 地标访问
题目描述
贝西在一条道路上旅行，道路上有许多地标，贝西想要在日落之前访问尽可能多的路标。将道路视为一条数轴，贝西从原点出发，道路上有n(1<=n<=50000)个地标，每个地标有一个坐标x[i](-100,000 ≤ xi ≤ 100,000)且地标的坐标各不相同，t(1≤ T ≤1000000000)分钟之后将会日落。
思路：
最暴力的解法是枚举所有地标区间，然后判断最大的访问地标数。但是可能会超时，运用二分法，枚举负点，二分正点，得到答案。

#include<bits/stdc++.h>
#define intn long long
#define _0for(i, a) for(int i = 0; i < (a); ++i)
#define _1for(i, a) for(int i = 1; i <=(a); ++i)
using namespace std;
int x[50005];
int y[50005];
main(void)
{
	int t,n,p;
	int cnt1=0,cnt2=0;
	cin>>t>>n;
	_1for(i,n)
	{
		cin>>p;
		if(p>=0)x[++cnt1]=p;
		else y[++cnt2]=p;
	}
	sort(x+1,x+1+cnt1);
	sort(y+1,y+1+cnt2); 
	y[++cnt2]=0;
	int anss=0;
	_1for(i,cnt2)//y[i]为负点 
	{
		int fu=cnt2-i;
		int l=0;
		int r=cnt1;
		int cnt=0;
		
		int ans=0;
		while(l<=r)
		{
			int mid=(r+l)/2;//正点	
			if(x[mid]-y[i]+min(abs(x[mid]),abs(y[i]))<=t)
			{
				ans=max(fu+mid,ans);
				l=mid+1;
			}
			else 
			{
				r=mid-1;
			}
		}
		anss=max(anss,ans);
	}
	cout<<anss;
}