题目链接

跳房子

题目描述

跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。
跳房子的游戏规则如下:
在地面上确定一个起点,然后在起点右侧画$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 \geq d$时),他的机器人每次可以选择向右弹跳的距离为$1$,$2$,$3$,…,$d+g-2$,$d+g-1$,$d+g$。
现在小R希望获得至少$k$分,请问他至少要花多少金币来改造他的机器人。

输入格式

第一行三个正整数$n$,$d$,$k$,分别表示格子的数目,改进前机器人弹跳的固定距离,以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。
接下来$n$行,每行两个整数$x_i,s_i$,分别表示起点到第$i$个格子的距离以及第$i$个格子的分数。两个数之间用一个空格隔开。保证$x_i$按递增顺序输入。

输出格式

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

样例输入1

7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出1

2

样例输入2

7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2

样例输出2

-1

说明/提示

输入输出样例$1$说明

$2$个金币改进后, 小R的机器人依次选择的向右弹跳的距离分别为$2,3,5,3,4,3$先后到达的位置分别为$2,5,10,13,17,20$,对应$1,2,3,5,6,7$这$6$个格子。这些格子中的数字之和$15$即为小R获得的分数。

输入输出样例$2$说明

由于样例中$7$个格子组合的最大可能数字之和只有$18$,无论如何都无法获得$20$分

数据规模与约定

本题共$10$组测试数据,每组数据$10$分。
对于全部的数据满足$1 \le n \le 500000, 1 \le d \le 2000, 1 \le x_i, k \le 10^9, |s_i| \lt 10^5$。
对于第$1,2$组测试数据,$n \le 10$;
对于第$3,4,5$组测试数据,$n \le 500$
对于第$6,7,8$组测试数据,$d=1$

题解

题意:有$n$个格子,在你右边不同距离处,每个格子都有一个$value$,当你付了$g$个金币后,对于给定的$d$,你每次都可以跳到你右边距离你$\in [max(d-g),d+g]$的格子上,每跳到一个格子上都会得到这个格子上的$value$,可以随时结束,求$value$之和大于等于给定的$k$时$g$最小为多少。
看题目这应该是一道二分答案的题目,那么我们接下来的问题就是判断付了$g$个金币后达到的最大分数能否达到$k$,那么我们可以用dp,$dp[i]$表示到第$i$个格子最大可以获得的分数。
那么转移方程就很简单了:
$dp[i]=max(dp[k])+s[i]$,满足$x_k \in [x_i-d+g,x_i-d-g]$
但是这样的话时间复杂度就是$O(n^2logx)$,显然会T。
因为题目输入的时候$x_i$是递增的(虽然不递增的话自己排个序问题也不大),所以计算$dp$的时候$[x_i-d+g,x_i-d-g]$这个区间也是单调递增的,那么我们显然可以用单调队列优化一下,那么时间复杂度就变成了$O(nlogx)$。
上代码:

#include<bits/stdc++.h>
using namespace std;
int n,d;
long long k;
struct aa{
    int x;
    long long s;
}a[500009];
int ans;
long long dp[500009];
bool kk[500009];//表示这个格子是否能被走到
bool pd(int md){
    memset(dp,0,sizeof(dp));
    memset(kk,0,sizeof(kk));
    int l=0,r=-1;
    int mx=-1;
    for(int j=1;j<=n;j++){
        while(a[l].x+d+md<a[j].x) l++;
        r=max(r,l-1);
        if(mx<l){//如果max已经不在区间了,就重新比较
            mx=-1;
            for(int i=l;i<=r;i++)
                if(!kk[i] && (mx==-1 || dp[i]>=dp[mx])) mx=i;
        }
        while(a[r+1].x+max(1,d-md)<=a[j].x){
            r++;
            if(!kk[r] && (mx==-1 || dp[r]>=dp[mx])) mx=r;//区间右边界扩大时更新max
        }
        if(mx!=-1) dp[j]=dp[mx]+a[j].s;
        else kk[j]=1;
        if(mx!=-1 && dp[j]>=k) return 1;
    }
    return 0;
}
long long amx;
int main(){
    scanf("%d%d%lld",&n,&d,&k);
    for(int j=1;j<=n;j++){
        scanf("%d%lld",&a[j].x,&a[j].s);
        amx+=max(a[j].s,(long long)0);
    }
    if(amx<k) {printf("-1");return 0;}
    int l=0,r=max(a[n].x-d,d-1);
    while(l<=r){
        int mid=(l+r)/2;
        if(pd(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}