P2698 [USACO12MAR] 花盆 Flowerpot https://www.luogu.org/problemnew/show/P2698
一看标签........ 十分后悔
标签告诉你单调队列 + 二分了............
每次二分花盆长度, 蓝后开 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;
- }
来源: http://www.bubuko.com/infodetail-2996433.html