🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

🫔 LYA 的幸运游戏

问题描述

LYA 在玩一个有趣的游戏。游戏开始时，LYA 站在数轴原点 $(0,0)$ 的位置。游戏有 $n$ 个指令，每个指令都是一个整数。如果指令为正数 $x$，则 LYA 向右移动 $x$ 个单位；如果指令为负数 $-x$，则 LYA 向左移动 $x$ 个单位；如果指令为 $0$，则 LYA 不移动。

在游戏开始前，LYA 选定了一个幸运数 $m$。如果某个指令的数值等于 $m$，则 LYA 在执行这个指令时，移动的距离会额外增加 $1$ 个单位。

请你计算在执行完所有指令后，LYA 所到达过的最右侧的位置。

输入格式

第一行输入一个正整数 $n$ ( $1\le n\le 100$ )，代表指令的总个数。

第二行输入一个整数 $m$ ( $-100\le m\le 100$ )，代表 LYA 的幸运数。

第三行输入 $n$ 个整数，每个整数的取值范围均为 $[-100,100]$，代表 $n$ 个指令。

输出格式

输出一个整数，代表 LYA 所到达过的最右侧的位置。

样例输入 1

2
1
-5 1

样例输出 1

0

样例输入 2

5
-5
-5 1 6 0 -7

样例输出 2

1

数据范围

• $1\le n\le 100$
• $-100\le m\le 100$
• 对于每个指令 $x$，都满足 $-100\le x\le 100$

题解

本题可以通过模拟 LYA 执行指令的过程,记录她所到达过的最右侧位置来解决。

用一个变量$pos$来表示卢小姐当前的位置,初始时$pos=0$。另外用一个变量$maxPos$来记录卢小姐到达过的最右侧位置,初始时$maxPos=0$。

接下来,遍历每一个指令$x$:

• 如果$x$等于幸运数$m$,那么将$pos$的值增加$x+1$;
• 否则,将$pos$的值增加$x$。

在每次更新$pos$的值后,都将$maxPos$更新为$maxPos$和$pos$中的较大值。

遍历完所有指令后,$maxPos$的值即为卢小姐到达过的最右侧位置。

时间复杂度为$O(n)$,空间复杂度为$O(1)$。其中$n$为指令的个数。

参考代码

• Python

def solve():
    n = int(input())

    if n < 1 or n > 100:
        print(12345)
        return

    m = int(input())

    if m < -100 or m > 100:
        print(12345)
        return

    pos, max_pos = 0, 0

    instructions = list(map(int, input().split()))

    for x in instructions:
        if x < -100 or x > 100:
            print(12345)
            return

        pos += x

        if x == m:
            pos += 1 if x > 0 else -1

        max_pos = max(max_pos, pos)

    print(max_pos)

solve()

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n < 1 || n > 100) {
            System.out.println(12345);
            return;
        }

        int m = sc.nextInt();

        if (m < -100 || m > 100) {
            System.out.println(12345);
            return;
        }

        int pos = 0, maxPos = 0;

        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();

            if (x < -100 || x > 100) {
                System.out.println(12345);
                return;
            }

            pos += x;

            if (x == m) {
                pos += x > 0 ? 1 : -1;
            }

            maxPos = Math.max(maxPos, pos);
        }

        System.out.println(maxPos);
    }
}

#include <iostream>
using namespace std;

void solve() {
    int n;
    cin >> n;

    if (n < 1 || n > 100) {
        cout << 12345 << endl;
        return;
    }

    int m;
    cin >> m;

    if (m < -100 || m > 100) {
        cout << 12345 << endl;
        return;
    }

    int pos = 0, maxPos = 0;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        if (x < -100 || x > 100) {
            cout << 12345 << endl;
            return;
        }

        pos += x;

        if (x == m) {
            pos += x > 0 ? 1 : -1;
        }

        maxPos = max(maxPos, pos);
    }

    cout << maxPos << endl;
}

int main() {
    solve();
    return 0;
}