原题链接

题解

二分加动态维护区间最大值
注意设立变量的含义，改变变量值的规则

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll sum[500005]={0};
struct unit
{
    ll x,v;
    bool operator <(const unit &b) const{return b.v>v;}//
}room[500005];

ll n,d,k;
ll check(ll g)
{
    memset(sum,-0x3f,sizeof sum);//初始化，由于分数有负，所以赋无限小为未踏入
    sum[0]=0;//如果一步也不走，得到的分数为零

    priority_queue<unit> q;//维护的是线性改变区间内的最大值
    //不能初始放入00，因为虽然放入其他值的时候确保了距离大于d-g，但是零点没有，这就导致了q中违规出现了小于d-g的值0
    ll it=0;
    for(ll i=1;i<=n;i++)//遍历房子
    {
        while(it<i&&room[i].x-room[it].x>=max(1LL,d-g)) q.push({room[it].x,sum[it++]});//可以从哪个房子跳过来，细节，由于要求跳的长度至少为一，所以当d-g小于1的时候要判断
        //但是由于有it<i和递增输入的限制，这个不会触发错误
        //这里添加要放在删除前面，因为刚添加进去的不一定小于d+g,他只是小于前一个点的d+g
        while(q.size()&&room[i].x-q.top().x>d+g) q.pop();

        if(q.size()) sum[i]=max(sum[i],q.top().v+room[i].v);//经过删除和添加后，堆顶是最大值
        //printf("sum[%d] = %d\n",i,sum[i]);
        if(sum[i]>=k)return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>d>>k;

    for(ll i=1;i<=n;i++)  cin>>room[i].x>>room[i].v;//输入为升序

    room[0].x=0;
    ll l=-1,r=1e9+2;

    while(l<r-1)
    {
        ll mid=(l+r)/2;
        //printf("%d\n",mid);
        if(check(mid)) r=mid;
        else l=mid;
        //puts("\n");
    }

    if(l!=1e9+1) cout<<r<<endl;
    else puts("-1");//只有一次大于k都没有才会等于1e9+1
    return 0;
}