题解 P2698 【[USACO12MAR]Flowerpot S】

· · 题解

P2698

前言：本题赞最高的那篇题解已经写得很清楚了，但本蒟蒻还是花了不少时间去理解，我决定把一些可能造成障碍的地方再解释一下

题意简述

题目分析

首先看到这道题（和这道题的标签）就发现直接求解长度非常麻烦，可以二分区间长度再去判断。

但是再一想，就会发现所在的区间端点一定在水滴上。

为什么呢？ 因为我们的花盆是要碰到水滴才可以计算答案，在水滴外面的部分就浪费了，所以区间端点一定在水滴上。

那么原问题就转化为了：给出一段数 (y) ，选出最短的一段，使其中的 最大值-最小值 大于 d 。

那么怎么求这一段呢？一个暴力的解法是枚举左右端点。复杂度 O(n^2) ，T飞~。 另一种方法是用单调队列，这里和滑动窗口稍微有些不同。滑动窗口的区间长度是固定的，要就内部的最大（小）值；这里给出区间内部的条件，求长度。

我们可以采用一个“拉窗口”的方法，最开始左端点和右端点都在最左边。

【】

我们可以把

  1. 这个右端点不断往右拉，直到满足条件

【…………】

  1. 记录一下答案，然后把左端点往右拉一下

…【…………】

  1. 重复一二步骤，直到右端点到达右边界

因为左右端点都只是从左边移到右边，所以复杂度是 O(n) 的。

代码思路

这里我们不关注具体的 x 值而去记录点的编号，因为区间端点一定在水滴上。排序后编号小的 x 一定小，只在记录答案的时候通过编号查询具体 x 值。

我们用两个优先队列，一个存区间最大值，一个存区间最小值。

最外层循环拉左端点（因为要里面右端点移完再动左端点）

每次先用两个while循环更新队首,直到队首不在左端点左边（因为移动了左端点有一个点的值就不能用了）

然后第二层循环移动右端点，直到达到右边界或满足条件（最大值-最小值 > d）。

里面再用两个循环类似滑动窗口更新最大值队列和最小值队列（只要队中还有元素且新加入的元素比队尾大（维护最大值时为小）那么就队尾出队，不需要管队首出队（这是更新左端点做的事情））。

第二层循环结束后，如果满足条件就更新 ans 。（ans要初始化成一个很大的值）。

一切结束后如果 ans 还是初始值，就输出 “-1”，否则输出 ans 。

易错点

  1. 两个队首都要像滑动窗口那样设置为 1 。（表明队列中有元素）
  2. 要用结构体存输入（因为要按 x 排序）
  4. 判断是否有解
  5. 更新队首要让队首不在左端点左边（用 < 而不是 <=）。

详细注释代码

#include<bits/stdc++.h>
using namespace std;
void read(int &x){//快读 
    int f=1;x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
#define N 100010
int n,d,ans;
struct node{
    int x,y;
}a[N];
bool cmp(node aa,node bb){
    return aa.x<bb.x;
}
int p1[N],p2[N];//我写单调队列一般用 q[] 存具体值，用 p[]存位置 
int head1,head2,tail1,tail2;//队列 1存最大值，队列 2存最小值 
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+1+n,cmp);//排序 
    ans=0x3f3f3f3f;
    head1=head2=1;
    for(int le=0,r=0;le<=n;le++){//最外层循环拉左端点 
        while(head1<=tail1&&p1[head1]<le) head1++;//如果队首比左端点小，那么右移
        while(head2<=tail2&&p2[head2]<le) head2++;//因为排序过了，编号小x一定小 
        while(a[p1[head1]].y-a[p2[head2]].y< d && r<n){
            r++;
            while(head1<=tail1&&a[p1[tail1]].y<a[r].y) tail1--;
            p1[++tail1]=r;
            while(head2<=tail2&&a[p2[tail2]].y>a[r].y) tail2--;
            p2[++tail2]=r;//更新两个单调队列 
        }
        if(r!=n) ans=min(ans,a[r].x-a[le].x);//满足条件 
    } 
    if(ans>=0x3f3f3f3f){//判无解 
        printf("-1");return 0;
    }
    else{
        printf("%d",ans);
    }
}

蒟蒻写题解不易，若对你有帮助，点个赞呗