题目地址：洛谷：【P2698】[USACO12MAR]花盆Flowerpot – 洛谷

题目描述

老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。
每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着的最后1滴水结束，之间的时间差至少为D。
我们认为，只要水滴落到x轴上，与花盆的边沿对齐，就认为被接住。给出N滴水的坐标和D的大小，请算出最小的花盆的宽度W。

输入输出格式

输入格式：
第一行2个整数 N 和 D。
第2.. N+1行每行2个整数，表示水滴的坐标(x,y)。

输出格式：
仅一行1个整数，表示最小的花盆的宽度。如果无法构造出足够宽的花盆，使得在D单位的时间接住满足要求的水滴，则输出-1。

输入输出样例

输入样例#1：

4 5
6 3
2 4
4 10
12 15

输出样例#1：

2

说明

【样例解释】
有4滴水， (6,3), (2,4), (4,10), (12,15).水滴必须用至少5秒时间落入花盆。花盆的宽度为2是必须且足够的。把花盆放在x=4..6的位置，它可以接到1和3水滴, 之间的时间差为10-3 = 7满足条件。
【数据范围】
40%的数据：1 ≤ N ≤ 1000，1 ≤ D ≤ 2000；
100%的数据：1 ≤ N ≤ 100000，1 ≤ D ≤ 1000000，0≤x,y≤10^6。

题解

按照x对水滴排个序，维护一个单增和单降的单调队列，每次更新就从队首弹元素弹到刚好大于D，然后用队首队尾的元素x之差更新答案即可。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int n, d;
int que[MAXN], ql, qr;

struct Node {
    int x, y;
} drop[MAXN];

inline bool cmp(Node a, Node b) {
    return a.x < b.x;
}

int main() {
    n = readint(); d = readint();
    for(int i = 1; i <= n; i++) {
        drop[i].x = readint(); drop[i].y = readint();
    }
    std::sort(drop + 1, drop + n + 1, cmp);
    int ans = 1e9;
    ql = qr = 0;
    for(int i = 1; i <= n; i++) {
        while(ql < qr && drop[que[qr - 1]].y <= drop[i].y) qr--;
        que[qr++] = i;
        while(ql < qr && drop[que[ql + 1]].y - drop[que[qr - 1]].y >= d) ql++;
        if(drop[que[ql]].y - drop[que[qr - 1]].y >= d) 
            ans = std::min(ans, drop[que[qr - 1]].x - drop[que[ql]].x);
    }
    ql = qr = 0;
    for(int i = 1; i <= n; i++) {
        while(ql < qr && drop[que[qr - 1]].y >= drop[i].y) qr--;
        que[qr++] = i;
        while(ql < qr && drop[que[qr - 1]].y - drop[que[ql + 1]].y >= d) ql++;
        if(drop[que[qr - 1]].y - drop[que[ql]].y >= d) ans = 
            std::min(ans, drop[que[qr - 1]].x - drop[que[ql]].x);
    }
    printf("%d", ans == 1e9 ? -1 : ans);
    return 0;
}