洛谷3258：[USACO2012 MAR]Flowerpot 花盆—

https://www.luogu.org/problemnew/show/P2698#sub

老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。

每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着的最后1滴水结束，之间的时间差至少为D。

我们认为，只要水滴落到x轴上，与花盆的边沿对齐，就认为被接住。给出N滴水的坐标和D的大小，请算出最小的花盆的宽度W。

单调队列好题，参考洛谷题解。

emm……显然是单调队列，把x排个序，维护y的单调增，然后正反扫一遍，当y差值>=d更新答案并且弹出对首，当y不满足单调是弹出对尾。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int N=1e5+;

inline int read(){

    int X=,w=;char ch=;

    while(ch<''||ch>''){w|=ch=='-';ch=getchar();}

    while(ch>=''&&ch<='')X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int x,y;

}a[N],q[N];

bool cmp(node a,node b){

    return a.x<b.x;

}

int main(){

    int n=read(),d=read();

    for(int i=;i<=n;i++){

    a[i].x=read(),a[i].y=read();

    }

    sort(a+,a+n+,cmp);

    int l=,r=,ans=1e9;

    for(int i=;i<=n;i++){

    while(l<r&&q[r-].y>a[i].y)r--;

    q[r++]=a[i];

    while(l<r&&q[r-].y-q[l].y>=d){

        ans=min(ans,q[r-].x-q[l].x);

        l++;

    }

    }

    for(int i=n;i>=;i--){

    while(l<r&&q[r-].y>a[i].y)r--;

    q[r++]=a[i];

    while(l<r&&q[r-].y-q[l].y>=d){

        ans=min(ans,q[l].x-q[r-].x);

        l++;

    }

    }

    if(ans==1e9)puts("-1");

    else printf("%d\n",ans);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

洛谷3258：[USACO2012 MAR]Flowerpot 花盆——题解

最新文章

热门文章