🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 编程一对一辅导

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 50+ 套笔试题，笔试真题 会在第一时间跟新

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞！

🐛 本套是8.10日OPPO笔试的第二套试题，总体难度不大

1️⃣ 分析题，看着很复杂，其实性质很容易分析出来

2️⃣ 是一道位运算贪心题，比较容易发现贪心的性质

3️⃣ 前后缀分解计数，是笔试很喜欢考的一类题型

🥄 01.LYA的河流冒险

问题描述

LYA是一位勇敢的探险家，她来到了一条神秘的河流前。这条河流长度为 米，河面上散布着一些神奇的浮石。LYA站在河的左岸，她的目标是到达对岸（右岸）。

LYA发现她只能踩在浮石上或者站在岸边。她想知道，在确保能够到达对岸的前提下，她需要跨出的最长一步最短是多少米。这将帮助她评估这次冒险的难度。

输入格式

第一行输入一个整数 （），表示河流的长度（单位：米）。

第二行输入 个整数 （）。如果 ，表示该位置有浮石可以踩；如果 ，表示该位置是水流，不能踩。

输出格式

输出一个整数，表示LYA需要跨出的最长一步的最小值（单位：米）。

样例输入

5
0 1 1 0 1

样例输出

2

样例解释

如下图所示，LYA最长的一步至少为2米，因为从左岸到最近的浮石距离为2米。

数据范围

题解

本题的核心思路是找出相邻浮石之间的最大距离。我们可以遍历河流，记录每个浮石的位置，并计算相邻浮石之间的距离。同时，需要特别考虑从左岸到第一个浮石的距离，以及最后一个浮石到右岸的距离。最终答案是这些距离中的最大值。时间复杂度为 O(n)，空间复杂度为 O(1)。关键是要注意边界情况的处理。

参考代码

• Python

# 读取输入
n = int(input())  # 河流长度
stones = list(map(int, input().split()))  # 浮石分布

# 初始化变量
max_step = 0  # 最长步长
last_stone = -1  # 上一个浮石的位置

# 遍历河流
for i in range(n):
    if stones[i] == 1:  # 如果当前位置是浮石
        if last_stone == -1:  # 如果是第一个浮石
            max_step = max(max_step, i + 1)  # 更新最长步长（从左岸到第一个浮石）
        else:
            max_step = max(max_step, i - last_stone)  # 更新最长步长（相邻浮石间距离）
        last_stone = i  # 更新上一个浮石位置

# 检查最后一个浮石到右岸的距离
max_step = max(max_step, n - last_stone) if last_stone != -1 else n

# 输出结果
print(max_step)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();  // 河流长度
        int[] stones = new int[n];  // 浮石分布
        for (int i = 0; i < n; i++) {
            stones[i] = scanner.nextInt();
        }
        
        // 初始化变量
        int maxStep = 0;  // 最长步长
        int lastStone = -1;  // 上一个浮石的位置
        
        // 遍历河流
        for (int i = 0; i < n; i++) {
            if (stones[i] == 1) {  // 如果当前位置是浮石
                if (lastStone == -1) {  // 如果是第一个浮石
                    maxStep = Math.max(maxStep, i + 1);  // 更新最长步长（从左岸到第一个浮石）
                } else {
                    maxStep = Math.max(maxStep, i - lastStone);  // 更新最长步长（相邻浮石间距离）
                }
                lastStone = i;  // 更新上一个浮石位置
            }
        }
        
        // 检查最后一个浮石到右岸的距离
        maxStep = Math.max(maxStep, lastStone == -1 ? n : n - lastStone);
        
        // 输出结果
        System.out.println(maxStep);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;  // 读取河流长度
    
    vector<int> stones(n);
    for (int& stone : stones) {
        cin >> stone;  // 读取浮石分布
    }
    
    int max_step = 0;  // 最长步长
    int last_stone = -1;  // 上一个浮石的位置
    
    // 遍历河流
    for (int i = 0; i < n; ++i) {
        if (stones[i] == 1) {  // 如果当前位置是浮石
            if (last_stone == -1) {  // 如果是第一个浮石
                max_step = max(max_step, i + 1);  // 更新最长步长（从左岸到第一个浮石）
            } else {
                max_step = max(max_step, i - last_stone);  // 更新最长步长（相邻浮石间距离）
            }
            last_stone = i;  // 更新上一个浮石位置
        }
    }
    
    // 检查最后一个浮石到右岸的距离