蓝海网站建设,游戏介绍网站模板下载,睢县房产网站建设,厚街东莞网站建设目录1.青蛙过河1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围7.原题链接2.解题思路Ac_code1.C2.Java1.青蛙过河
1.题目描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃…
目录1.青蛙过河1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围7.原题链接2.解题思路Ac_code1.C2.Java1.青蛙过河
1.题目描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上某次跳跃 后使石头高度下降到 0 是允许的。
小青蛙一共需要去学校上 xxx 天课, 所以它需要往返 2x2x2x 次。当小青蛙具有 一个跳跃能力 yyy 时, 它能跳不超过 yyy 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 xxx 次课。
2.输入格式
输入的第一行包含两个整数 n,xn,xn,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x2x2x 才是实际过河的次数。 第二行包含 n−1n−1n−1 个非负整数 H1,H2,⋯,Hn−1H_1,H_2,⋯,H_{n-1}H1,H2,⋯,Hn−1, 其中 Hi0H_i0Hi0表 示在河中与 小青蛙的家相距 iii 的地方有一块高度为 HiH_iHi 的石头, Hi0H_i 0Hi0 表示这个位置没有石头。
3.输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
4.样例输入
5 1 1 0 1 0
5.样例输出
4
6.数据范围
1≤n≤105,1≤x≤109,1≤Hi≤104。1≤n≤10^5 ,1≤x≤10^9,1≤H i ≤10^ 4 。1≤n≤105,1≤x≤109,1≤Hi≤104。
7.原题链接
青蛙过河
2.解题思路
假设青蛙可以按照某条路线SSS从家跳往对岸路线SSS上所有的石子高度均减1这个操作等价于“青蛙从对岸按照路线SSS反向跳回家路线SSS上所有的石子高度均减1”。
这也说明判断小青蛙能否往返2x2x2x次等价于判断小青蛙能否从左往右跳重复2x2x2x次。
由题目可以发现设小青蛙的跳跃能力为yyy当小青蛙跳跃能力yyy越大越容易满足“重复2x次”的约束即求解的yyy存在单调性
当yyy越大时小青蛙每次可以跳的范围更大可以跳更少的步数到达对岸即更容易重复2x2x2x次当ynynyn时无需经过任何石子就可以跳到对岸。当yyy越小时小青蛙需要使用更多的步数才能到达对岸更不容易满足“重复2x2x2x次”的约束。
本题最终需要求解的是恰好满足约束的最小的yyy 答案存在单调性显然可以用二分答案的算法进行求解初始区间[l,r][1,n][l,r][1,n][l,r][1,n]
求出区间[l,r][l,r][l,r]的中点midmidmidmid(lr)//2mid(lr)//2mid(lr)//2判断当小青蛙跳跃能力等于midmidmid时能否从左往右跳重复2x2x2x次 如果可以则更新ansmidansmidansmid调整搜索区间为[l,mid−1][l,mid-1][l,mid−1]求最小值因此调整右端点否则调整搜索区间为[mid1,r][mid1,r][mid1,r] 如果lrl rlr终止循环否则回到111
二分答案将求解最值问题转换成判定性问题问题转变成当跳跃能力等于yyy时判断小青蛙能否从左往右跳2x2x2x次。
小青蛙最开始位于0处跳跃能力等于yyy需要重复跳跃2x2x2x次则首先要求从1−y1-y1−y的石子高度必须大于等于2x2x2x不然小青蛙迈出的第一步都无法重复2x2x2x次。
这个结论可以推广——“所有长度为yyy的区间中石子高度之和必须大于等于2x2x2x”。
如果所有长度为yyy的区间中石子高度之和等于2x:2x:2x:则存在HiHiyH_iH_{iy}HiHiy则只要保证第一步在[1,y][1,y][1,y]中选择一个可以跳跃的石子iii则后续跳跃只需从当前位置iii跳到iyiyiy即可。这样可以保证重复2x2x2x次如果所有长度为yyy的区间中石子高度之和大于2x2x2x**则可以考虑去除某些石子的高度从而构造出情况1此时也是可以保证重复2x2x2x次的如果可以重复跳跃2x2x2x次所有区间长度为yyy的区间中石子高度之和大于等于2x2x2x对于任意区间[i,iy][i,iy][i,iy]每次跳跃必须在区间中落脚。利用反证法如果不在区间[i,iy][i,iy][i,iy]中落脚等价于从iii的左边跳到了iyiyiy的右边此时跳跃长度超过了能力上限yyy因此不合法。也就是说每次跳跃对于任意长度等于yyy的区间都落脚1次重复2x2x2x次则说明该区间石子之和大于等于2x2x2x。
通过上面三点可以证明“当跳跃能力等于yyy时重复2x2x2x次”等价于“所有区间长度等于yyy的区间石子高度之和大于等于2x2x2x”利用这个结论进行二分答案的判定即可。
实现过程中事先预处理前缀和从而可以O(1)O(1)O(1)求解区间和时间复杂度O(nlogn)O(n\log n)O(nlogn)。
实际上使用双指针维护区间和始终大于 2x2x2x得到的最小区间长度则是答案这样可做到 O(n)O(n)O(n) 的复杂度。
Ac_code
1.C
#includebits/stdc.h
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairint, int PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf 0x3f3f3f3f;
const int mod 1000000007;
const int N 200010;LL n, x;
void solve()
{cin n x;std::vectorLL s(n 1);for (int i 1; i n; i) {cin s[i];s[i] s[i - 1];}//最后一块石头也就是终点可以无限跳s[n] 1e18;int l 1, r n;auto check [](int g) {for (int i 0; i g n; i) {int r i g;if (s[r] - s[i] 2 * x) return false;}return true;};while (l r) {int mid l r 1;if (check(mid)) r mid;else l mid 1;}cout r \n;
}
int main()
{ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t 1;while (t--){solve();}return 0;
}2.Java
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scnew Scanner(System.in);int nsc.nextInt();long xsc.nextLong();long []arrnew long[n1];for (int i1;in;i){arr[i]sc.nextLong()arr[i-1];}arr[n]100000000000L;int l0;int ans0;for (int r1;rn;r){if (arr[r]-arr[l] 2*x){ansMath.max(ans,r-l);l1;}}System.out.println(ans);}
}
