题目链接

解题思路

这题挺有意思的，看一看是可以在20分钟内想到解法，但是在实现的过程中会遇到很多阻碍。
乍一看题面，问的是“至少”，那可以判断出这题大概率是道二分答案题。然后看子任务，在二分的答案下找到最优解，这个就贪心或者DP。想了会儿贪心不可行就去推DP了。
这题DP也很好推，就是 $dp[i]=dp[j]+s[i]$ ，其中j能够跳到i。
但是很明显这样做是 $O(n^2logn)$ 的。所以我们要引进单调队列优化。（这之前我一直以为单调队列优化是优先队列优化，于是TLE了好几回）
我们不难发现，在对于i的可选决策中，有一些实可以延续到j的。而如果离i近的比离i远的DP[j]大，那肯定选DP[j]，因为远的那个点又远又小，没有竞争力。
单调队列优化就此解决，但是我们发现它不是从0-y都能跳，而是从x-y能跳。所以我们需要一个数组保存从0-x的待选决策。
这样这道题就结束了

代码

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e16;
long long dp[500005];
int x[500005];
int s[500005];
struct kkk{
    int pos;
    long long sum;
};
deque<kkk> q;
kkk dai[5000005];
int dl=1,dr=0;
int n,d,k;
bool check(long long mid){//要用两个priority_queue存储待存区间和可用区间 
    int addmin,addmax;
    if(mid<d){
        addmin=d-mid;
        addmax=d+mid;
    }else{
        addmin=1;
        addmax=d+mid;
    }
    while(!q.empty())q.pop_back();
    dl=1,dr=0;
    for(int i=1;i<=n;i++)dp[i]=-inf;
    kkk now,nxt;
    for(int i=1;i<=n;i++){
        long long ans=-inf;
        while(dl<=dr&&dai[dl].pos<=x[i]-addmin){
            if(dai[dl].pos<x[i]-addmax){//再也取不到了 
                dl++;
            }else{
                while(!q.empty()){
                    if(q.back().sum<=dai[dl].sum)q.pop_back();
                    else break;
                }
                q.push_back(dai[dl]);//可用 
                dl++;
            }
        }
        while(!q.empty()){//太远了，之后也不可能跳到
            if(q.front().pos<x[i]-addmax){//再也取不到 
                q.pop_front();
            }else if(!q.empty()){
                ans=max(ans,q.front().sum);//可取，直接用 
                break;
            }
        }
        dp[i]=ans+s[i];
        if(x[i]>=addmin&&x[i]<=addmax)dp[i]=max(dp[i],(long long)s[i]);
        nxt.pos=x[i];
        nxt.sum=dp[i];
        dai[++dr]=nxt;
    }
    long long maxn=-inf;
    for(int i=1;i<=n;i++){
        maxn=max(maxn,dp[i]);
    }
    if(maxn>=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]);
    }
    long long l=0,r=1e9+7,mid;
    long long ans=-1;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }else{
            l=mid+1;
        }
    }
    printf("%d",ans);
    return 0;
}

本文链接：http://kaispace.com.cn/index.php/archives/747/

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者