题解 | #单调队列#

V题

题意：给n个雨滴的坐标（x,y），问花坛的宽度至少为多少，才能使得ymax - ymin $\ge \backslash ge$ d.

思路：先二分答案，后面该思考怎么check，check里主要给你一个长度mid，你要求在这个长度内的max(ymax - ymin)，所以考虑用单调队列去求给定长度内的最大值与最小值，之后就能统计结果了。

但不知为什么样例4-6给的宽度是2，所以我在check里先mid++;

using namespace std;

const int N = 1e5 + 5;
struct node{
    int x, y;
    bool operator<(const node b) const{
        if (x != b.x) return x < b.x;
        else return y < b.y;
    }
}a[N];
int n, d;
int ma[N], mi[N], q[N];

bool check(int mid)
{
    mid++;
    int head = 1, tail = 0, f = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && a[q[head]].x < max(1, a[i].x - mid + 1)) head++;
        while (head <= tail && a[i].y >= a[q[tail]].y) tail--;
        q[++tail] = i;
        if (a[i].x >= mid) ma[f++] = a[q[head]].y;
    }
    
    head = 1, tail = 0, f = 0;
    for (int i = 1; i <= n;i ++) {
        while (head <= tail && a[q[head]].x < max(1, a[i].x - mid + 1)) head++;
        while (head <= tail && a[i].y <= a[q[tail]].y) tail--;
        q[++tail] = i;
        if (a[i].x >= mid) mi[f++] = a[q[head]].y;
    }
    int ans = 0;

    for (int i = 0; i < f; i++) {
        ans = max(ans, ma[i] - mi[i]);
//         cout << ma[i] << " " << mi[i] <<'\n';
    }
    return ans >= d;
}

int main()
{
    cin >> n >> d;
    int ma = 0, mi = 1e8;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y; 
        ma = max(ma, a[i].y), mi = min(mi, a[i].y);
    }
    
    if (ma - mi < d) {
        cout << -1;
        return 0;
    }
    sort(a + 1, a + 1 + n);
    
    int l = 1, r = ma;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    cout << r;
    return 0;
}