🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁~
🍓OJ题目截图
文章目录
- 📎在线评测链接
- 🍓OJ题目截图
- 🫔 LYA 的幸运游戏
- 问题描述
- 输入格式
- 输出格式
- 样例输入 1
- 样例输出 1
- 样例输入 2
- 样例输出 2
- 数据范围
- 题解
- 参考代码
🫔 LYA 的幸运游戏
问题描述
LYA 在玩一个有趣的游戏。游戏开始时,LYA 站在数轴原点 ( 0 , 0 ) (0,0) (0,0) 的位置。游戏有 n n n 个指令,每个指令都是一个整数。如果指令为正数 x x x,则 LYA 向右移动 x x x 个单位;如果指令为负数 − x -x −x,则 LYA 向左移动 x x x 个单位;如果指令为 0 0 0,则 LYA 不移动。
在游戏开始前,LYA 选定了一个幸运数 m m m。如果某个指令的数值等于 m m m,则 LYA 在执行这个指令时,移动的距离会额外增加 1 1 1 个单位。
请你计算在执行完所有指令后,LYA 所到达过的最右侧的位置。
输入格式
第一行输入一个正整数 n n n ( 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100 ),代表指令的总个数。
第二行输入一个整数 m m m ( − 100 ≤ m ≤ 100 -100 \le m \le 100 −100≤m≤100 ),代表 LYA 的幸运数。
第三行输入 n n n 个整数,每个整数的取值范围均为 [ − 100 , 100 ] [-100,100] [−100,100],代表 n n n 个指令。
输出格式
输出一个整数,代表 LYA 所到达过的最右侧的位置。
样例输入 1
2
1
-5 1
样例输出 1
0
样例输入 2
5
-5
-5 1 6 0 -7
样例输出 2
1
数据范围
- 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100
- − 100 ≤ m ≤ 100 -100 \le m \le 100 −100≤m≤100
- 对于每个指令 x x x,都满足 − 100 ≤ x ≤ 100 -100 \le x \le 100 −100≤x≤100
题解
本题可以通过模拟 LYA 执行指令的过程,记录她所到达过的最右侧位置来解决。
用一个变量 p o s pos pos来表示卢小姐当前的位置,初始时 p o s = 0 pos=0 pos=0。另外用一个变量 m a x P o s maxPos maxPos来记录卢小姐到达过的最右侧位置,初始时 m a x P o s = 0 maxPos=0 maxPos=0。
接下来,遍历每一个指令 x x x:
- 如果 x x x等于幸运数 m m m,那么将 p o s pos pos的值增加 x + 1 x+1 x+1;
- 否则,将 p o s pos pos的值增加 x x x。
在每次更新 p o s pos pos的值后,都将 m a x P o s maxPos maxPos更新为 m a x P o s maxPos maxPos和 p o s pos pos中的较大值。
遍历完所有指令后, m a x P o s maxPos maxPos的值即为卢小姐到达过的最右侧位置。
时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( 1 ) O(1) O(1)。其中 n n n为指令的个数。
参考代码
- Python
def solve():n = int(input())if n < 1 or n > 100:print(12345)returnm = int(input())if m < -100 or m > 100:print(12345)returnpos, max_pos = 0, 0instructions = list(map(int, input().split()))for x in instructions:if x < -100 or x > 100:print(12345)returnpos += xif x == m:pos += 1 if x > 0 else -1max_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;
}