[题解]luogu_P3957跳房子（单调队列

虽然是道普及的题，一眼看出二分单调队列，但是我不会写单调队列

不能再套板子了，必须要理解灵活

用一个指针j维护窗口的右端点，每次移动时把多出来那部分的扫一下塞进去，取队头前把左端点左边的弹掉

各种算法都没有完全固定的写法！

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500009;
int n,d,k;
int s[maxn],q[maxn];
ll x[maxn],f[maxn];
bool check(int g){
    for(int i=0;i<=n;i++)f[i]=-1e18;
    int hd=1,tl=0,j=0;
    q[1]=0;f[0]=0;
    int l=max(d-g,1),r=d+g;
    
    for(int i=1;i<=n;i++){
        while(x[i]-l>=x[j]&&j<i){
            if(f[j]!=-1e18){
                while(hd<=tl&&f[q[tl]]<=f[j])tl--;
                q[++tl]=j;
            }
            j++;
        }
        while(hd<=tl&&x[i]-r>x[q[hd]])hd++;
        if(hd<=tl)f[i]=f[q[hd]]+s[i];
        if(f[i]>=k)return 1;
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&d,&k);
    for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&s[i]);
    int l=0,r=x[n];
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    if(check(l))printf("%d",l);
    else printf("-1");
}