[USACO12MAR] 花盆

题意

给定 n 个点 和一个整数 ,求一个最小区间 ,使得点集 中的纵坐标的极差 最大.

输出区间长度 .

.

分析

将点按横坐标排序

二分答案,单调队列找最小最大值判断即可

代码

#include<cstdio>
#include<algorithm>
#include<deque>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N=1e6;
int n,d;
pii a[N];
bool check(int k){deque<pii> qmin,qmax;
    int pos=0,di=0;
    while(pos<n){
        ++pos;
        while(qmin.size()&&qmin.front().x+k<a[pos].x)qmin.pop_front();
        while(qmin.size()&&qmin.back().y>=a[pos].y)qmin.pop_back();
        qmin.push_back(a[pos]);
        while(qmax.size()&&qmax.front().x+k<a[pos].x)qmax.pop_front();
        while(qmax.size()&&qmax.back().y<=a[pos].y)qmax.pop_back();
        qmax.push_back(a[pos]);
        di=max(di,qmax.front().y-qmin.front().y);
    }
    return di>=d;
}
int main(){scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);//y,x
    sort(a+1,a+n+1);
    int l=0,r=1000001,mid;
    while(l<r){mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%d",l==1000001?-1:l);
    return 0;
}

  转载请注明: Sshwy's Blog [USACO12MAR] 花盆

 上一篇
斜率优化 DP 入门 斜率优化 DP 入门
前言本蒟蒻的第一道斜率优化 DP 前后卡了 3 小时…… 海星 有时候好不容易推出一个 DP 的式子,结果发现数据范围太大? 单调队列无法优化? 那就考虑斜率优化吧 [APIO2014] 序列分割 你正在玩一个关于长度为 的非负整
2019.01.15
下一篇 
[NOI2009] 变换序列 [NOI2009] 变换序列
题意在 的整数序列中,定义两个数 的距离为 . 现要求构造一个序列 ,使得每一个
2019.01.15
  目录