滑动窗口+二分--P3957 跳房子

* 思路：$dp_i$表示到第$i$个格子的最大得分，仔细思考后发现$f_i$只能从他之前一段区间内的最大$f_i$转移过来，且随着区域的后移不断改变，滑动窗口维护再二分答案就好了。

*代码实现：

滑动窗口的活动范围：$max$($d-len$,1)$ o$$d+len$
滑动窗口的移动：当最大值的位置超过了他能跳到的最远距离，则head++,窗口右移，另外如果我队尾的元素小于我现在加入的元素，那么队尾元素对答案没有贡献，弹出就好了，则tail--
```
while (head<=tail&&dp[now]>=dp[q[tail]]) tail--;
      q[++tail]=now,now++;
while (head<=tail&&x[q[head]]<x[i]-maxlen) head++;
```
注意如果当前点不能到达要直接跳过
```
if (dp[now]<=-1e9) {now++;continue;}
```
二分答案：按升序的花费二分，如果当前花费无法满足总和大于$k$，那么前面的也一定不满足，则找右区间，如果当前花费满足总和大于$k$，那么后面的也一定满足，则找左区间，满足二分的单调性和局部舍弃性。
```
 while (l<r){
    int mid=(l+r)>>1;
    if (solve(mid)) tag=1,r=mid;
    else l=mid+1;
  }
```

完整代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #define int long long
 5 using namespace std;
 6 const int maxn=5e5+10;
 7 int n,d,k;
 8 int x[maxn],s[maxn],q[maxn],dp[maxn];
 9 bool tag=0;
10 bool solve(int len){
11   int now=0,head=1,tail=0,maxlen=len+d,minlen=max(d-len,1ll*1);
12   for (int i = 1;i <= n;i++){
13     while (x[now]<=x[i]-minlen){
14       if (dp[now]<=-1e9) {now++;continue;}
15       while (head<=tail&&dp[now]>=dp[q[tail]]) tail--;
16       q[++tail]=now,now++;
17     }
18     while (head<=tail&&x[q[head]]<x[i]-maxlen) head++;
19     if (head<=tail) dp[i]=dp[q[head]]+s[i];
20     else dp[i]=-1e9;
21     if (dp[i]>=k) return 1;
22   }
23   return 0;
24 }
25 signed main(){
26   scanf ("%lld%lld%lld",&n,&d,&k);
27   for(int i = 1;i <= n;i++) scanf("%lld%lld",&x[i],&s[i]);
28   int l=0,r=500000;
29   while (l<r){
30     int mid=(l+r)>>1;
31     if (solve(mid)) tag=1,r=mid;
32     else l=mid+1;
33   }
34   if (tag) printf("%lld
",r);
35   else printf("-1
");
36   return 0;
37 }