最新华为OD机试真题-LYA 的幸运游戏(100分)

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

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

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

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> LYA 的幸运游戏(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

LYA 的幸运游戏

问题描述

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

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

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

输入格式

第一行输入一个正整数 ( )，代表指令的总个数。

第二行输入一个整数 ( )，代表 LYA 的幸运数。

第三行输入 个整数，每个整数的取值范围均为 ，代表 个指令。

输出格式

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

样例输入 1

2
1
-5 1

样例输出 1

0

样例输入 2

5
-5
-5 1 6 0 -7

样例输出 2

1

数据范围

• 对于每个指令 ，都满足

题解

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

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

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

• 如果等于幸运数,那么将的值增加;
• 否则,将的值增加。

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

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

时间复杂度为,空间复杂度为。其中为指令的个数。

参考代码

• 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;
}