首页 > 其他 > 详细

P2698 [USACO12MAR]花盆Flowerpot(单调队列+二分)

时间:2019-03-22 21:52:07      阅读:173      评论:0      收藏:0      [点我收藏+]

P2698 [USACO12MAR]花盆Flowerpot

一看标签........十分后悔

标签告诉你单调队列+二分了............

每次二分花盆长度,蓝后开2个单调队列维护最大最小值

蓝后就是code了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int Max(int a,int b){return a>b?a:b;}
void read(int &x){
    static char c=getchar();x=0;
    while(c<0||c>9) c=getchar();
    while(0<=c&&c<=9) x=x*10+(c^48),c=getchar();
}
#define N 100005
struct data{int x,y;}a[N];
inline bool cmp(data A,data B){return A.x<B.x;}
int n,d,h1[N],h2[N],L1,R1,L2,R2;
bool check(int len){
    int re=0; L1=L2=1; R1=R2=0;
    for(int i=1;i<=n;++i){
        while(L1<=R1&&a[h1[L1]].x<a[i].x-len) ++L1;
        while(L2<=R2&&a[h2[L2]].x<a[i].x-len) ++L2;
        while(L1<=R1&&a[h1[R1]].y>=a[i].y) --R1;
        while(L2<=R2&&a[h2[R2]].y<=a[i].y) --R2;
        h1[++R1]=h2[++R2]=i;
        re=Max(re,a[h2[L2]].y-a[h1[L1]].y);
    }return re<d;
}
int main(){
    read(n);read(d);
    for(int i=1;i<=n;++i) read(a[i].x),read(a[i].y);
    sort(a+1,a+n+1,cmp);
    int l=1,r=1000000;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    if(check(l)) puts("-1");
    else printf("%d",l);
    return 0;
}

 

P2698 [USACO12MAR]花盆Flowerpot(单调队列+二分)

原文:https://www.cnblogs.com/kafuuchino/p/10581123.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!