[杂题]:B/b(二分答案)
阅读原文时间:2023年07月11日阅读:2

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


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


样例输入:

6 2
1 5
2 6

样例输出:

1


样例解释:

最优方案是在$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
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(xl[i]?maxn:l[i];
minn=minni)
{
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>1;
if(judge(mid))rht=mid;
else lft=mid+1;
}
printf("%d",lft);
return 0;
}


rp++