B/b.cpp:表达式化简，二分答案

不知道能不能粘题面于是不粘了。

首先声明这道题可以怎么水过：

随机化几万次操作，取最优答案。

暴力O(n²log n)可过。

不想打正解的可以走了。

emm然而我的应该是正解，O(n log n)。

首先不难想到二分答案，判断最大距离是mid是否可行。

假设决策点是x，y。

那么对于所有的点对（p,q）有5种走法。

直接走。q-p；

其余情况都是走到x再跳到y再走到q。是abs(x-p)+abs(y-q)

拆开。

若p<x,y<q,是q-p-y+x

若p<x,y>q,是-p-q+y+x

若p>x,y<q,是p+q-x-y

若p>x,y>q,是p-q-x+y

而这些值都不能大于mid。

那么对于所有q-p>mid的点对，如果它满足那个带abs的式子，那么它一定同时满足这4个式子。

列成不等式组，其实就是A<=x+y<=B,C<=x-y<=D的形式

那么我们只要判定$B_{min}>=A_{max}$且$D_{min}>=C_{max}$即可。

推荐自己手推一下式子。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int n,m,l[],r[];

 bool check(int x){

     int m00=-,m01=-,m10=-,m11=-;

     for(int i=;i<=m;++i)if(r[i]-l[i]>x)m00=max(m00,l[i]+r[i]),m01=max(m01,l[i]-r[i]),

         m10=max(m10,r[i]-l[i]),m11=max(m11,-l[i]-r[i]);

     return x-m11>=m00-x&&x-m10>=m01-x;

 }

 int main(){

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

     for(int i=;i<=m;++i)scanf("%d%d",&l[i],&r[i]);

     int ll=,rr=n;

     while(ll<rr-)if(check(ll+rr>>))rr=ll+rr>>;else ll=(ll+rr>>)+;

     if(check(ll))printf("%d\n",ll);else printf("%d\n",rr);

 }

巴特西

B/b.cpp:表达式化简，二分答案

最新文章

热门文章