【题目描述】
跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。 跳房子的游戏规则如下： 在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定： 玩家每次都必须跳到当前位置右侧的一个格子内 。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。 现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人，如果他花 g 个金币改进他的机器人，那么他的机器人灵活性就能增加 g，但是需要注意的是，每次弹跳的距离至少为 1。具体而言，当g<d时，他的机器人每次可以选择向右弹跳的距离为 d−g,d−g+1,d−g+2，…，d+g−2，d+g−1，d+g；否则（当g≥d时），他的机器人每次可以选择向右弹跳的 距离为 1，2，3，…，d+g−2，d+g−1，d+g。 现在小 R 希望获得至少 k 分，请问他至少要花多少金币来改造他的机器人。

【输入】
第一行三个正整数 n，d，k，分别表示格子的数目，改进前机器***跳的固定距离，以及希望至少获得的分数。相邻两个数之间用一个空格隔开。

接下来 n 行，每行两个正整数xi,si，分别表示起点到第i个格子的距离以及第i个格子的分数。两个数之间用一个空格隔开。保证xi按递增顺序输入。

【输出】
共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获 得至少 k 分，输出−1。

【输入样例】
7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
【输出样例】
2
【提示】
【输入输出样例 1 说明】 花费 2 个金币改进后，小 R 的机器人依次选择的向右弹跳的距离分别为 2，3，5，3，4，3，先后到达的位置分别为 2，5，10，13，17，20，对应 1,2,3,5,6,7 这 6 个格子。这些格子中的数字之和 15 即为小 R 获得的分数。

输入：
7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2
输出:
-1

【输入输出样例 2 说明】
由于样例中 7 个格子组合的最大可能数字之和只有 18 ，无论如何都无法获得 20 分。

【数据规模与约定】
本题共 10 组测试数据，每组数据 10 分。
对于全部的数据满足1≤n≤500000,1≤d≤2000,1≤xi,k≤109,|si|<105。
对于第 1，2 组测试数据，n≤10；
对于第 3，4，5 组测试数据，n≤500;
对于第 6，7，8 组测试数据，d=1。
NOIP2017普及组第4题

分析：
这道题的算法单调队列+二分+dp，时间复杂度为O（n+log（1e9））。
如果所有正分的总和都没k高的话，输出-1，结束程序。
判断金币最少用多少个改造使用二分算法。
dp[i]表示已第i个为终点，最大的分数。
单调队列是求一段区间内的极值（最大值）。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,d,fen,sum=0,dp[500005];
struct node
{
    ll zuobiao,zhi;
} a[500005];
int f(int g)
{
    deque<int> dq;
    int i,pre=0,l=max(1ll,d-g),r=d+g;
    for(i=1; i<=n+1; i++)
    {

        while(a[i].zuobiao-a[pre].zuobiao>=l)
        {
            if(dp[pre]==-1e9)
            {
                pre++;
                continue;
            }
            while(!dq.empty()&&dp[dq.back()]<=dp[pre])
                dq.pop_back();
            dq.push_back(pre);
            pre++;
        }
        while(!dq.empty()&&a[dq.front()].zuobiao+r<a[i].zuobiao)
            dq.pop_front();
        if(!dq.empty())
            dp[i]=dp[dq.front()]+a[i].zhi;
        if(dp[i]>=fen)
            return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    ll i,j,best=0;
    cin>>n>>d>>fen;
    for(i=1; i<=n; i++)
    {
        cin>>a[i].zuobiao>>a[i].zhi;
        sum+=max(0ll,a[i].zuobiao);
    }
    if(sum<fen)
    {
        cout<<-1<<endl;
        return 0;
    }
    ll l=0,r=1000000007,mid;
    while(l<=r)
    {
        for(i=1; i<=500005; i++)
            dp[i]=-1e9;
        int pre=0;
        mid=(l+r)/2;
        if(f(mid))
            best=mid,r=mid-1;
        else
            l=mid+1;
    }
    cout<<best<<endl;
    return 0;

}