蒟蒻不会单调队列，怎么办？另类方法，一样AC

题目要我们求最小的，这看上去就不太好直接求。怎么办？

一个常见的想法，将原问题转换成判定性问题:给定弹跳距离的范围，能否获得至少分。(注意:玩家可以在任意时刻结束游戏，所以只要出现一个时刻的分数满足即可）

一个朴素的想法:可以DP!

每次找前面合法状态(即符合弹跳距离)中当前分数最大的状态转移。

，朴素的枚举好像会挂。怎么优化？

注意到每次事实上有用的只有分数最大的那个状态，想到了啥？

RMQ?优先队列？(我也不知道为啥想到的不是单调队列而是优先队列)

想到这里那么这一题已经基本做完了。

用优先队列维护所有合法状态，每次取出堆顶转移即可。

实测不开O2可以AC

也许我的做法比较平易近人

/*
    Author:Frozencode
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 500010;
const ll INF = 2147483647;
struct node{
    ll pos,pts;
}a[maxn];//pts为该点得分。
struct tem{
    ll pos,sum;
    bool operator < (const tem &a)const//结构体优先队列必备之重载运算符。
    {
        return sum < a.sum;
    }
};//sum为当前的分数。
priority_queue<tem>q;
priority_queue<tem>iq;
tem cur;
ll n,d,k,l,r,res;
void init(ll i,ll x){
    while(!q.empty()){
        cur = q.top();
        if(a[i].pos - cur.pos > d + x){q.pop();}//剔除不合法状态
        else if(a[i].pos - cur.pos < max(1ll * 1,d - x)){
            iq.push(q.top());
            q.pop();
        }//对于当前状态此状态不合法，但是以后的状态可能会用到，得先留着。
        else break;//发现最大值，转移走起。
    }
    return;
}
bool check(ll x){
    while(!q.empty())q.pop();
    while(!iq.empty())iq.pop();
    cur.pos = 0;
    cur.sum = 0;
    q.push(cur);//以上为初始化。
    for(int i = 1;i <= n;i++){
        init(i,x);
        if(q.empty())
        {
            while(!iq.empty()){
            q.push(iq.top());
            iq.pop();
            }
            continue;//没法转移，此状态拜拜~ 还原现场。
        }
        cur.pos = a[i].pos;
        cur.sum = cur.sum + a[i].pts;
        if(cur.sum >= k)return true;//符合条件 成功！
        q.push(cur);//添加新状态。
        while(!iq.empty()){
            q.push(iq.top());
            iq.pop();
        }还原现场。
    }
    return false;//失败 T_T
}
int main()
{ 
    ios::sync_with_stdio(false);
    cin>>n>>d>>k;
    for(int i = 1;i <= n;i++){
        cin>>a[i].pos>>a[i].pts;
        r = max(r,a[i].pos);
    }
    l = res = -1;//如果答案一次都没更新到说明无论如何都没法达到k分。输出-1。
    ++r;
    while(l < r - 1){
        ll mid = (l + r)>>1;
        if(check(mid)){
            r = mid;
            res = r;//更新答案。
        }
        else l = mid;
    }//二分没啥好说的。
    cout<<res;
    return 0;
}

后话:这种做法其实是可以被卡到的，所以只有在实在想不到别的做法的时候可以一试。

你以为这就结束了？NO!

作为一道单调队列板子题，怎么能不用单调队列做呢（雾

由上面的分析可得，用deque维护所有合法状态，可以解决这个问题。

/*
    Author:Frozencode
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 500010;
const ll INF = 2147483647;
struct node{
    ll pos,pts;
}a[maxn];
deque<ll> q;
ll n,d,k,l,r,res,dp[maxn];
bool check(ll x){
    memset(dp,128,sizeof(dp));
    while(!q.empty())q.pop_front();
    dp[0] = 0;
    ll cur = 0;
    for(int i = 1;i <= n;i++)
    {
        while(cur < i && a[i].pos - a[cur].pos >= max(1ll * 1,d - x)){//合法状态进队。
            while(!q.empty() && dp[q.back()] <= dp[cur])q.pop_back();//比当前状态劣就弹出。
            q.push_back(cur);
            cur++;
        }
        while(!q.empty() && a[i].pos - a[q.front()].pos > d + x)q.pop_front();//不合法状态出队。
        if(!q.empty())dp[i] = dp[q.front()] + a[i].pts;
        if(dp[i] >= k)return true;
    }
    return false;
}
int main()
{ 
    ios::sync_with_stdio(false);
    cin>>n>>d>>k;
    for(int i = 1;i <= n;i++){
        cin>>a[i].pos>>a[i].pts;
        r = max(r,a[i].pos);
    }
    l = res = -1;
    ++r;
    while(l < r - 1){
        ll mid = (l + r)>>1;
        if(check(mid)){
            r = mid;
            res = r;
        }
        else l = mid;
    }
    cout<<res;
    return 0;
}