[杂题]:B/b（二分答案）

题目传送门（内部题53）

输入格式

第二行$2$个整数表示$n,m$。
接下来$m$行每行两个整数，描述一个点对$(x_i,y_i)$。

输出格式

一个整数，表示最短距离。

样例

样例输入：

6 2
1 5
2 6

样例输出：

数据范围与提示

样例解释：

最优方案是在$2$号节点和$5$号节点之间建边。

数据范围：

对于前$30\%$的数据：
$n,m\leqslant 500$
对于前$60\%$的数据：
$n,m\leqslant 2,000$
对于所有数据：
$1\leqslant n,m\leqslant 100,000$
$1\leqslant x_i\leqslant y_i\leqslant n$

题解

发现答案是满足单调性的，假设答案为$d$，那么比$d$小的一定都不行，比$d$大的一定都行。

所以我们考虑二分答案，如何$judge$呢？

正解我不会，于是我打的暴力，枚举端点和点对，然后疯狂简枝，下面列举一下剪枝：

　　$\alpha.$二分范围，所有点对取$\max$即可。

　　$\beta.$在枚举点队的时候，已经满足的不用考虑，所以我们每一次先扫一边，将还没有满足的点对提取出来。

　　$\gamma.$如果不满足的点对的右端点的最小值比左端点的小，那么也一定不行，直接$return\ 0$即可。

这三个剪枝一个也不能少。

时间复杂度：$\Theta(n^2\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

int l[100001],r[100001],len[100001];

int que[100001];

bool judge(int x)

{

	int minn=n,maxn=0,rmin=n,lft,rht;

	que[0]=0;

	for(int i=1;i<=m;i++)

		if(x<len[i])

		{

			que[++que[0]]=i;

			rmin=rmin<r[i]?rmin:r[i];

			maxn=maxn>l[i]?maxn:l[i];

			minn=minn<l[i]?minn:l[i];

		}

	if(!que[0])return 1;

	if(rmin<=maxn)return 0;

	for(int i=minn;i<=maxn;i++)

	{

		lft=0;

		rht=n;

		for(int j=1;j<=que[0];j++)

		{

			if(r[que[j]]>i)

			{

				int flag=x-abs(l[que[j]]-i);

				lft=max(lft,r[que[j]]-flag);

				rht=min(rht,r[que[j]]+flag);

				if(lft>rht)goto nxt;

				continue;

			}

			goto nxt;

		}

		return 1;

		nxt:;

	}

	return 0;

}

int main()

{

	scanf("%d%d",&n,&m);

	int lft=0,rht=0;

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d",&l[i],&r[i]);

		len[i]=r[i]-l[i];

		rht=rht>len[i]?rht:len[i];

	}

	while(lft<rht)

	{

		int mid=(lft+rht)>>1;

		if(judge(mid))rht=mid;

		else lft=mid+1;

	}

	printf("%d",lft);

	return 0;

}

rp++

巴特西