题目描述

难度:[蓝]提高+/省选-

输入$n(1 \leq n \leq 5 \times 10^5)$、$d(1 \leq d \leq 2000)$、$k(1 \leq k \leq 10^9)$和$n$个$pair$，每个$pair$输入两个数$x_i(1 \leq x_i \leq 10^9)$和$s_i(-10^5 \leq s_i \leq 10^5)$。保证$x_i$是递增的。

坐标轴上有$n$个点，$x_i$是点的位置，$s_i$是到达这个点可以得到的分数。

在游戏的开始，你可以花费$g$个金币强化你的跳跃能力，使你可以从$x$跳到在$[x+max(d-g,1), x+d+g]$中的点。

注意在游戏的过程中，不能花费金币强化能力。注意你必须跳到输入的$n$个点中，不能跳到其他位置。你从原点$0$开始向右跳。你可以在任意时刻结束游戏。

目标是让总得分$\geq k$。输出$g$的最小值。如果无法做到，输出$-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

算法

二分答案+单调队列优化DP

比较容易发现单调性，因为$g$越大，意味着每次跳跃能够选择的下一步范围就越大，这样就更有可能得到更大的分数，因此我们可以二分这个最佳的$g$。对于一个给定的$g$，DP求能够得到的最大分数。

1. 只要这个分数$\geq k$，那这个$g$就是可以的，记录答案并往左搜索看能不能更小；
2. 否则$g$就太小了，往右搜索更大的$g$。

状态定义

对于一个给定的$g$，从前往后$i \in [1,n]$进行DP。$dp[i]$表示从$0$跳到$i$的最大得分，那只要$max_{i \in [1,n]}dp[i] \geq k$就说明当前的$g$可以。

状态转移

在当前位置为$i$的情况下，它的上一个位置可能是$[x-d-g,x-max(d-g,1)]$，发现这是一个固定长度的窗口，本质上是一个区间去最大值的问题，状态转移方程为$dp[i]=max_{x-d-g \leq x[j] \leq x-max(d-g,1)}dp[j]+s[i]$。

这里最开始我想到的是线段树存$dp$，$O(log_2n)$求区间最值，但是这样会使得整个算法的时间复杂度为$O(log_2Unlog_2n)$，其中$U$是$x$的值域，在这个数据范围下莽不过去。但是还有一种比较经典的区间最值求法——单调队列，这样时间复杂度被优化至$O(nlog_2U)$，就可以过了。

复杂度分析

时间复杂度

二分答案在$x$的值域上进行，时间复杂度为$O(log_2U)$；对于每个$g$，需要用单调队列来优化DP，时间复杂度为$O(n)$。因此，整个算法的时间复杂度为$O(nlog_2U)$。

空间复杂度

除了输入的各种数组，空间瓶颈在于DP数组$dp$，以及单调队列的那个队列。空间复杂度取决于状态数量，而状态数量是$O(n)$级别，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 500010;
int n, d, k, x[N], s[N];
LL dp[N];

bool check(int g) {
    for(int i = 0; i <= n; i++) {
        dp[i] = 0;
    }
    LL mx = -1e15;
    deque<int> q;
    for(int i = 1, high = 0; i <= n; i++) {
        int L = x[i] - d - g, R = x[i] - max(d - g, 1);
        while(high <= n && x[high] <= R) {
            while(!q.empty() && dp[q.back()] < dp[high]) {
                q.pop_back();
            }
            q.push_back(high++);
        }
        while(!q.empty() && x[q.front()] < L) {
            q.pop_front();
        }
        if(!q.empty()) {
            dp[i] = s[i] + dp[q.front()];
        }else {
            dp[i] = -1e15;
        }
        if(dp[i] > mx) {
            mx = dp[i];
        }
    }
    return mx >= k;
}

int main() {
    scanf("%d%d%d", &n, &d, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &s[i]);
    }
    int l = 0, r = x[n], ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        }else {
            l = mid + 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}