解法与正确性

贪心：在每一步，若能跳 2 就优先跳 2；否则跳 1。 理由：两步跳比一步跳更“划算”，且跳 2 不会阻断可达性（题意保证存在解）。若某处能跳 2 却选择跳 1，只会增加一次额外跳跃而不带来任何好处，因此始终优先跳 2 是最优。

复杂度分析

• 时间复杂度：O(n)，每个位置最多检查一次。
• 空间复杂度：O(1)，仅常数额外变量。

代码实现

Python

# 读取所有输入并求解，中文注释
import sys

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    c = list(map(int, data[1:1+n]))
    i = 0
    ans = 0
    while i < n - 1:
        # 若可以跳两步且是积云，则优先跳两步
        if i + 2 < n and c[i + 2] == 0:
            i += 2
        else:
            i += 1
        ans += 1
    print(ans)

if __name__ == "__main__":
    solve()

Java

// 贪心解法：能跳2就跳2，否则跳1
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        // 读 n
        s = br.readLine();
        while (s != null && s.trim().isEmpty()) s = br.readLine();
        int n = Integer.parseInt(s.trim());
        // 读数组
        String line = br.readLine();
        while (line != null && line.trim().isEmpty()) line = br.readLine();
        StringTokenizer st = new StringTokenizer(line);
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            if (!st.hasMoreTokens()) { // 若换行，继续读
                line = br.readLine();
                if (line == null) break;
                st = new StringTokenizer(line);
            }
            c[i] = Integer.parseInt(st.nextToken());
        }
        int i = 0, ans = 0;
        while (i < n - 1) {
            if (i + 2 < n && c[i + 2] == 0) i += 2;
            else i += 1;
            ans++;
        }
        System.out.println(ans);
    }
}

C++

// 贪心：优先跳两步
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) cin >> c[i];
    int i = 0, ans = 0;
    while (i < n - 1) {
        if (i + 2 < n && c[i + 2] == 0) i += 2;
        else i += 1;
        ++ans;
    }
    cout << ans << "\n";
    return 0;
}

题目内容

有一个新的手机游戏，里面有很多不同的云其中一些云是雷云，其他都是积云。

玩家可以跳上任何一个编号与当前云加 $1$ 或 $2$ 相等的积云。而玩家必须避开雷云。请确定从起始位置跳到最后一朵云需要的最小跳数。

假设玩家总是可以赢得游戏。

对于每个游戏，你会得到一个数组，其中编号为 $0$ 的云表示是积云，编号为 $1$ 的云表示需要雷云。

示例：

$c= [0,1,0,0,0,1,0]$ 假设索引从 $0$ 开始。玩家必须避开索引为 $1$ 和 $5$ 的云。

他们可以选择以下两条路径：$0->2->4->6$ 或 $0->2->3->4->6$ 。

第一条路径需要 $3$ 次跳跃或 $0->2->3->4->6$ 。

第一条路径需要 $3$ 次跳跃而第二条路径需要 $4$ 次跳跃。

返回 $3$ 。

输入描述

第一行包含一个整数 $n$ ，表示云的总数。

第二行包含 $n$ 个以空格分隔的二进制整数，描述云 $c[i]$ 的情况，其中 $0<=i<n$ 。

约束条件：

$2 <=n <= 100$

$c[i]$ 取值为 {$0,1$}

$c[0] == c[n-1]== 0$

输出描述

打印赢得游戏所需的最小跳数。

样例1

输入

7
0 0 1 0 0 1 0

输出

4

说明

玩家必须避开 $c[2]$ 和 $c[5]$ 。

游戏最少需要 $4$ 次跳跃。

样例2

输入

6
0 0 0 0 1 0

输出

3

说明

只需要避开 $c[4]$ 。

游戏最少需要 $3$ 次跳跃。