题目链接
https://www.luogu.com.cn/problem/P8775
题目大意
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 \(1\)，当石头的高度下降到 \(0\) 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 \(0\) 是允许的)。
小青蛙一共需要去学校上 \(x\) 天课，所以它需要往返 \(2x\) 次。当小青蛙具有一个跳跃能力 \(y\) 时，它能跳不超过 \(y\) 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 \(x\) 次课。
解题思路
不妨看一下 CF965D Single-use Stones 这道题，然后你就会发现两道题目几乎一摸一样。
本题只是在 CF965D 的基础上加了一个二分。
两道题最主要要解决的问题都是一样的，就是：
如何计算当跳跃能力为 \(k\) 时最多能够上多少次课。
解决这个问题的方法有很多，我使用的是 贪心，思路是这样的：
当跳跃能力为 \(k\) 时，对于第 \(i\) 块石头，能跳到它的石头对应的区间是 \([i-k, i-1]\)，此时必然优先选下标小的。为什么呢？因为如果 \(i-k\) 和 \(i-k+1\) 都可以选择，我选择 \(i-k\) 必然更优，因为留下来的 \(i-k+1\) 还可以跳到第 \(i+1\) 个石头，但是如果留下来 \(i-k\)，是不能跳到第 \(i+1\) 个石头的。所以，对于第 \(i\) 块石头，优先选择下标 \(i\) 的石头作为其前一步的石头能够导致我的剩余局面最优，符合贪心思想。
那么，同样的道理反过来思考，如果我当前在第 \(i\) 个石头，我能够跳到的石头的区间范围是 \([i+1, i+k]\)，我也会优先选择下标大的那个石头跳过去。
所以可以设计一个 cal(k) 函数，其返回跳跃能力为 \(k\) 时最多能够上多少次课。
然后，答案的区间范围是 \([1, n]\)，所以在区间 \([1, n]\) 范围内二分判断 cal(k) >= 2*x 就能够找到能上至少 \(2x\) 次课的最低跳跃能力了。
示例程序
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, x, h[maxn], c[maxn];
int cal(int k) {
memset(c, 0, sizeof(int)*(n+1));
h[0] = c[0] = h[n] = 2e9;
stack<int> stk;
for (int i = 1; i < k; i++) stk.push(i);
for (int i = 0; i < n; i++) {
if (i+k <= n && h[i+k]) stk.push(i+k);
while (c[i] && !stk.empty() && stk.top() > i) {
int j = stk.top();
// i --> j
int t = min(c[i], h[j] - c[j]);
c[i] -= t;
c[j] += t;
if (c[j] == h[j]) stk.pop();
}
}
return c[n];
}
int main() {
cin >> n >> x;
for (int i = 1; i < n; i++) cin >> h[i];
int l = 1, r = n, res;
while (l <= r) {
int mid = (l + r) / 2;
if (cal(mid) >= 2 * x) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << res << endl;
return 0;
}
原文地址：http://www.cnblogs.com/quanjun/p/16845423.html
