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

• 算法结构

目录

  • 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.样例输出

4

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.原题链接

青蛙过河

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
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair 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 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);
    }
}

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/28b73223b9.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐