问题描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的)。
小青蛙一共需要去学校上 xx 天课, 所以它需要往返 2x2x 次。当小青蛙具有 一个跳跃能力 yy 时, 它能跳不超过 yy 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 xx 次课。
输入格式
输入的第一行包含两个整数 n,xn,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x2x 才是实际过河的次数。
第二行包含 n−1n−1 个非负整数 H1,H2,⋯,Hn−1H1,H2,⋯,Hn−1, 其中 Hi>0Hi>0 表示在河中与 小青蛙的家相距 ii 的地方有一块高度为 HiHi 的石头, Hi=0Hi=0 表示这个位置没有石 头。
输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
样例输入
5 1
1 0 1 0
样例输出
4
样例说明
由于只有两块高度为 11 的石头，所以往返只能各用一块。第 11 块石头和对岸的距离为 44，如果小青蛙的跳跃能力为 33 则无法满足要求。所以小青蛙最少需要 44 的跳跃能力。
评测用例规模与约定
对于 30%30% 的评测用例, n≤100n≤100;
对于 60%60% 的评测用例, n≤1000n≤1000;
对于所有评测用例, 1≤n≤105,1≤x≤109,1≤Hi≤1041≤n≤105,1≤x≤109,1≤Hi≤104 。
#include<iostream>
#include<vector>
using namespace std;
int n, x;
vector<int> h(1000000,0);
vector<int> sum(1000000, 0);//前缀和便于计算区间和
//本题思路很简单，假设跳跃值看能不能满足条件
//重点是如何判断是否成功？
/*假设此刻jump为3
岸，1，2，3，|4，5，6，|7，8，9，岸
从起始岸蹦一步/两步/三步分别到1,2,3
所以第一跳一定在1,2,3，任意一个之间，所以1,2,3高度和要>=2x
在1时，下一步只能走到4去，因此，想要容纳1全部的被踩次数，4号的石头高度应>=1号，[1,3]总高度>=2x，
又因4号高度>=1号高度，故区间[2,4]高度之和>=2x，以此类推.
可以证明，要想总过河次数>=2x，任一石头编号i开始，长度为步长的区间[i,i+步长-1]石头总高度之和>=2x
*/
bool check(int j) {for (int i = 1; i <= n-j; i++) {//一共n-1个石头，不是n个，所以是n-1-j+1=n-jint count = sum[i + j - 1] - sum[i - 1];if (count < 2 * x) return false;}return true;
}
int main()
{cin >> n >> x;for (int i = 1; i <= n - 1; i++) {cin >> h[i];sum[i] = sum[i - 1] + h[i];}int l = 1;int r = n;while (l < r) {int middle = (l + r) / 2;if (check(middle)) {r = middle;}else {l = middle + 1;}}cout << l;return 0;
}
