Skip to content

二分

P1663

二分当前的yy坐标，有三种情况：

1.两个点一样高，y坐标相同，则只要yy小于y就不满足

2.左点低右点高，则根据两点表示直线，xx应为

\[ \frac{x_2-x_1}{y_2-y_1}=\frac{xx-x_1}{yy-y_1} \\ xx=\frac{x_2-x_1}{y_2-y_1}* (yy-y_1)+x_1 \]

那么R=min(R,xx)

3.左边高，同理，L=max(L,xx)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const double P=0.001,INF=1000001.0;
const int N=1e5+10;
struct node{
    double x,y;
}q[N];
int n;
bool check(double y){
    double L=0,R=INF;
    for(int i=2;i<=n;++i){
        if(q[i].y==q[i-1].y){
            if(y<q[i].y)return false;
        }
        else if(q[i].y>q[i-1].y){
            double x1=q[i-1].x,x2=q[i].x,y1=q[i-1].y,y2=q[i].y;
            double x=((x2-x1)/(y2-y1))*(y-y1)+x1;
            R=min(R,x);
        }
        else{
            double x1=q[i-1].x,x2=q[i].x,y1=q[i-1].y,y2=q[i].y;
            double x=((x2-x1)/(y2-y1))*(y-y1)+x1;
            L=max(L,x);
        }
    }
    return L<=R;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf%lf",&q[i].x,&q[i].y);
    }
    double l=0.0,r=INF,ans=-1.0;
    while(l+P<=r){
        double mid=(l+r)/2.0;
        if(check(mid)){
            r=mid;
            ans=mid;
        }else l=mid+P;
    }
    printf("%.2lf",ans);
    return 0;
}

P1661

二分时间，判断(曼哈顿距离+1)/2是否小于等于当前的时间，满足就将两个点用并查集连接，最后检查是否都并在一个点上即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=55,INF=1e10;
int abs1(int x){return x>0?x:-x;}
int dis(int x1,int y1,int x2,int y2){return abs1(x1-x2)+abs1(y1-y2);}
struct node{
    int x,y;
}q[N];
int n;
int fa[N],vis[N];
int getfa(int u){
    if(fa[u]==u)return u;
    return fa[u]=getfa(fa[u]);
}
bool check(int x){
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<n;++i){
        for(int j=i+1;j<=n;++j){
            int d=dis(q[i].x,q[i].y,q[j].x,q[j].y),t=(d+1)>>1;
            if(t<=x)fa[getfa(i)]=getfa(j);
        }
    }
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;++i)vis[getfa(i)]++;
    for(int i=1;i<=n;++i)if(vis[i]>=n)return true;
    return false;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld%lld",&q[i].x,&q[i].y);
    int ans=0,l=0,r=INF;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid;
            ans=mid;
        }else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}

P7514

可以二分一下极差\(x\)，并枚举一下区间\([L,L+x]\),其中\(L\)可以是所有正反面中的任意值，一共\(2n\)个。因为所有的\(a_i\)是单增的，所有不在区间的数一定构成前后缀，那么这些卡牌一定要翻面，并且翻完面的\(b_i\)也要在区间内，所以这样枚举就可以将问题转化成前后缀的\(RMQ\)最大和最小是否都在区间内，以及前后缀是否超过了\(m\)个数。确定前后缀的位置可以双指针爬一下维护，是\(O(n)\)的。\(RMQ\)也是\(O(n)\)的(\(st\)表)，所以总复杂度\(O(n\log n)\)

~~大常数选手表示很淦~~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010,K=21,INF=1e9+10;
struct node{
    int a,b;
}a[N];

int n,m,cnt;
int b[N+N],Log[N],Max[N][K],Min[N][K];
int read1(){
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
bool cmp(int a,int b){
    return a<b;
}
void init(){
    Log[1]=0;
    for(int i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(int i=1;i<=n;++i) Max[i][0]=Min[i][0]=a[i].b;
    for(int j=1;(1<<j)<=n;++j)
        for(int i=1;i+(1<<(j-1))<=n;++i)
            Min[i][j]=INF,Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]),Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
}
int query(int t,int l,int r){
    if(l>r){
        if(!t) return INF;
        else return 0;
    }
    int k=Log[r-l+1];
    if(!t) return min(Min[l][k],Min[r-(1<<k)+1][k]);
    else return max(Max[l][k],Max[r-(1<<k)+1][k]);
} 
bool check(int x){
    bool flag=false;
    int l=1,r=0,L=0,R=0,_min=0,_max=0,tot=0;
    for(int i=1;i<=cnt;++i){
        L=b[i],R=b[i]+x;
        while(a[l].a<L && l<=n) ++l;
        while(a[r+1].a<=R && r+1<=n) ++r;
        tot=l-1+n-r;
        if(tot>m)continue;
        _min=min(query(0,1,l-1),query(0,r+1,n)),_max=max(query(1,1,l-1),query(1,r+1,n));
        if(_min<L || _max>R)continue;
        if(_min>=L && _max<=R){
            flag=true;break;
        }
    }
    return flag;
}

int main(){
    //freopen("P7514_9.txt","r",stdin);
    n=read1(),m=read1();cnt=0;
    for(int i=1;i<=n;++i) a[i].a=read1(),b[++cnt]=a[i].a;
    for(int i=1;i<=n;++i) a[i].b=read1(),b[++cnt]=a[i].b;
    sort(b+1,b+cnt+1,cmp);
    init();
    int l=0,r=b[cnt]-b[1],ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}