第十三届蓝桥杯省赛 C++ A 组 F 题、Java A 组 G题、C组 H 题、Python C 组 I 题——青蛙过河（AC）

爱被打了一巴掌 2023-09-29 20:07 20阅读 0赞

#### 目录 ####

*  1.青蛙过河
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题链接
     *  2.解题思路
 *  Ac\_code
 *   *  1.C++
     *  2.Java

## 1.青蛙过河 ##

### 1.题目描述 ###

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 `1` , 当石头的高度下降到 `0` 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到`0` 是允许的）。

小青蛙一共需要去学校上  x x x 天课, 所以它需要往返  2 x 2x 2x 次。当小青蛙具有 一个跳跃能力  y y y 时, 它能跳不超过  y y y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完  x x x 次课。

### 2.输入格式 ###

输入的第一行包含两个整数  n , x n,x n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意  2 x 2x 2x 才是实际过河的次数。  
第二行包含  n − 1 n−1 n−1 个非负整数  H 1 , H 2 , ⋯ , H n − 1 H\_1,H\_2,⋯,H\_\{n-1\} H1,H2,⋯,Hn−1, 其中  H i > 0 H\_i>0 Hi>0表 示在河中与 小青蛙的家相距  i i i 的地方有一块高度为  H i H\_i Hi 的石头,  
 H i = 0 H\_i =0 Hi=0 表示这个位置没有石头。

### 3.输出格式 ###

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

### 4.样例输入 ###

5 1  
1 0 1 0

### 5.样例输出 ###

### 6.数据范围 ###

1 ≤ n ≤ 1 0 5 , 1 ≤ x ≤ 1 0 9 , 1 ≤ H i ≤ 1 0 4 。 1≤n≤10^5 ,1≤x≤10^9,1≤H i ≤10^ 4 。 1≤n≤105,1≤x≤109,1≤Hi≤104。

### 7.原题链接 ###

[青蛙过河][Link 1]

### 2.解题思路 ###

假设青蛙可以按照某条路线 S S S从家跳往对岸，路线 S S S上所有的石子高度均减1，这个操作等价于“青蛙从对岸按照路线 S S S反向跳回家，路线 S S S上所有的石子高度均减1”。

这也说明，判断小青蛙能否往返 2 x 2x 2x次，等价于**判断小青蛙能否从左往右跳重复 2 x 2x 2x次**。

由题目可以发现，设小青蛙的跳跃能力为 y y y，当小青蛙跳跃能力 y y y越大，越容易满足“**重复2x次**”的约束，即求解的 y y y存在单调性：

*  当 y y y越大时，小青蛙每次可以跳的范围更大，可以跳更少的步数到达对岸，即更容易重复 2 x 2x 2x次，当 y = n y=n y=n时，无需经过任何石子就可以跳到对岸。
 *  当 y y y越小时，小青蛙需要使用更多的步数才能到达对岸，更不容易满足“重复 2 x 2x 2x次”的约束。

本题最终需要求解的是：**恰好满足约束的最小的** y y y 答案存在单调性，显然可以用二分答案的算法进行求解，初始区间 \[ l , r \] = \[ 1 , n \] \[l,r\]=\[1,n\] \[l,r\]=\[1,n\]：

1.  求出区间 \[ l , r \] \[l,r\] \[l,r\]的中点 m i d mid mid， m i d = ( l + r ) / / 2 mid=(l+r)//2 mid=(l\+r)//2
2.  判断当小青蛙跳跃能力等于 m i d mid mid时，能否从左往右跳重复 2 x 2x 2x次
    
    1.  如果可以，则更新 a n s = m i d ans=mid ans=mid，调整搜索区间为 \[ l , m i d − 1 \] \[l,mid-1\] \[l,mid−1\]（求最小值，因此调整右端点）
    2.  否则，调整搜索区间为 \[ m i d + 1 , r \] \[mid+1,r\] \[mid\+1,r\]
3.  如果 l > r l > r l>r，终止循环，否则回到 1 1 1

二分答案将求解最值问题转换成判定性问题，问题转变成**当跳跃能力等于 y y y时，判断小青蛙能否从左往右跳 2 x 2x 2x次。**

小青蛙最开始位于0处，跳跃能力等于 y y y，需要重复跳跃 2 x 2x 2x次，则首先要求从 1 − y 1-y 1−y的石子高度必须大于等于 2 x 2x 2x，不然小青蛙迈出的第一步都无法重复 2 x 2x 2x次。

这个结论可以推广——“所有长度为 y y y的区间中石子高度之和必须大于等于 2 x 2x 2x”。

1.  **如果所有长度为** y y y**的区间中**，**石子高度之和等于** 2 x : 2x: 2x:则存在 H i = H i + y H\_i=H\_\{i+y\} Hi=Hi\+y，则只要保证第一步在 \[ 1 , y \] \[1,y\] \[1,y\]中选择一个可以跳跃的石子 i i i，则后续跳跃只需从当前位置 i i i跳到 i + y i+y i\+y即可。这样可以保证重复 2 x 2x 2x次；
2.  **如果所有长度为** y y y**的区间中，石子高度之和大于** 2 x 2x 2x：\*\*则可以考虑去除某些石子的高度，从而构造出情况1，此时也是可以保证重复 2 x 2x 2x次的；
3.  **如果可以重复跳跃** 2 x 2x 2x**次，所有区间长度为** y y y**的区间中石子高度之和大于等于** 2 x 2x 2x：对于任意区间 \[ i , i + y \] \[i,i+y\] \[i,i\+y\]，每次跳跃必须在区间中落脚。利用反证法，如果不在区间 \[ i , i + y \] \[i,i+y\] \[i,i\+y\]中落脚，等价于从 i i i的左边跳到了 i + y i+y i\+y的右边，此时跳跃长度超过了能力上限 y y y，因此不合法。也就是说，每次跳跃对于任意长度等于 y y y的区间都落脚1次，重复 2 x 2x 2x次则说明该区间石子之和大于等于 2 x 2x 2x。

通过上面三点可以证明：“当跳跃能力等于 y y y时重复 2 x 2x 2x次”等价于“所有区间长度等于 y y y的区间石子高度之和大于等于 2 x 2x 2x”，利用这个结论进行二分答案的判定即可。

实现过程中事先预处理前缀和，从而可以 O ( 1 ) O(1) O(1)求解区间和，时间复杂度 O ( n log ⁡ n ) O(n\\log n) O(nlogn)。

实际上使用双指针，维护区间和始终大于  2 x 2x 2x，得到的最小区间长度则是答案，这样可做到  O ( n ) O(n) O(n) 的复杂度。

## Ac\_code ##

### 1.C++ ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair<int, 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::vector<LL> 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 sc=new Scanner(System.in);
            int n=sc.nextInt();
            long x=sc.nextLong();
            long []arr=new long[n+1];
            for (int i=1;i<n;i++){
        
                arr[i]=sc.nextLong()+arr[i-1];
            }
            arr[n]=100000000000L;
            int l=0;
            int ans=0;
            for (int r=1;r<=n;r++){
        
                if (arr[r]-arr[l]>= 2*x){
        
                    ans=Math.max(ans,r-l);
                    l+=1;
                }
            }
            System.out.println(ans);
        }
    }

[Link 1]: https://www.lanqiao.cn/problems/2097/learning/