遍历打擂台寻找最大值,需要使用 `long long` 防止大整数溢出,并注意记录第一次出现的位置。
OJ: roj
题目 ID: 5040
难度:入门
标签:数组模拟
创建: 2026-10-08 23:13
更新: 2026-10-08 23:13
形式化题目
给定一个长度为
正解
思路
本题的本质是一个打擂台求最大值及对应位置的题目。我们需要从前往后遍历序列,用变量记录当前遇到的最大数值的下标 max_pos(和其对应的值 max_val)。
每遇到一个元素 max_pos = i。因为只有在严格大于时才更新,所以如果遇到相同的最大值,不会覆盖第一次记录的位置,这天然满足了题目「并列时取第一次出现位置」的隐含需求。
这道题的核心陷阱在于数值范围:
题面说明“每个数在 int 类型能表示的最大正整数为 INT_MAX 的值(如 cin >> int 来读取,由于读入的值超出了 int 的上界,cin 不会发生“回绕成负数”的现象,而是会将该变量钳位为 INT_MAX(failbit。这会导致此后所有的读入全部失败(读入值为 0),从而把最大值错误地“冻结”在已经成功读入的前缀里,结果与真实值无关,必然算错。
(如果是 scanf("%d") 或对 long long 读入后强制转 (int),则会发生真实的截断回绕现象,例如 long long。相对而言,Python 支持任意精度的大整数,因此使用 Python 的整型不会存在溢出问题。
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:57
# update_at: 2026-10-08 22:57
import sys
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
# 打擂台:依次消费每个数,严格大于当前最大值才更新位置,
# 因此并列最大值保留第一次出现的位置。Python 整数无溢出问题,
# 题面值域上界 2^32-1 直接可装。
max_pos = 1
max_val = next(data)
for i in range(2, n + 1):
value = next(data)
if value > max_val:
max_val = value
max_pos = i
print(max_pos)
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 22:57
* update_at: 2026-10-08 22:57
*/
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
// a[1..n]:题面的输入序列。用 ll 存:题面值域上界 2^32-1 超过 INT_MAX,int 会溢出。
ll a[MAXN];
// 读入 n 个数存入 a[1..n],打擂台求最大值所在位置(1-based)。
void solve() {
ll n;
cin >> n;
for (ll i = 1; i <= n; ++i) {
cin >> a[i];
}
ll max_pos = 1; // 当前最大值所在位置,从 a[1] 起打擂台
for (ll i = 2; i <= n; ++i) {
// 只有严格大于才更新位置,故并列最大值保留第一次出现的位置
if (a[i] > a[max_pos]) {
max_pos = i;
}
}
cout << max_pos << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}复杂度
- 时间复杂度:
。我们需要遍历 个数进行比较,每次比较的操作时间是常数的。 - 空间复杂度:
。本题在代码实现中,开辟了数组 a[1..n]来储存输入的数据,空间消耗随数据规模线性增长。
总结
- 数值范围与类型(本题核心):
- 本题中数据的最大值达到了
。实测显示数据点 2、5、6、8、9、10 均含有超过 INT_MAX的值。 cin >> int的行为与溢出危害:在处理超限数据时,cin >> int不会像scanf或强转那样回绕成负数,而是会把值钳位在INT_MAX并且置位failbit。一旦置位,后续所有的读入均会被忽略。实验表明,如果本题把变量类型换成int,会导致个测试点直接错误(输出的位置错误地停留在由于报错而停止读取的前面部分)。 - 为什么不用
unsigned int?:虽然unsigned int的上限刚好是,但在打擂台算法中,我们通常需要一个初值。如果沿用习惯的无符号负一初值 max_val = (unsigned)(-1),其值等于—— 恰好等于题面上限。这会导致没有任何一个元素能大于这个哨兵值,导致 全错(全输出 )。直接用数组第一个元素作初值可以规避,但为了稳妥且遵守项目规范,统一使用 long long处理超过int的数据更加安全。
- 本题中数据的最大值达到了
- 并列最大值的处理:题面只规定了输出“最大数所在位置”,但未对多个相同的最大值做显式说明。通过实测验证:
- 在全相等的测试点(如
p9,1000 个),输出是 1。 - 在最大值出现多次的测试点(如
p7,最大值出现 24 次,最先出现在位置 116),输出为116。 - 结论:并列时应当输出第一次出现的位置。我们在条件判断中使用严格大于 (
>) 天然契合这一逻辑。
- 在全相等的测试点(如
- 1-based 编号与末尾位置验证:
- 题面明确提到“存放在数组
至 中”,因此要遵循 1-based 索引。样例输出以及最大值出现在末尾的测试点(如 p10的最大值恰好在第 1000 位,正确输出了1000)都证实了输出位置不应减 1。
- 题面明确提到“存放在数组
- 验证强度:
- 异源验证:采用 Python 的内置
max()加index()算法与 C++ 的单遍流式打擂台算法对比,对 373 组穷举测试点(, 取值 加上边界点)实现了 0 分歧。 - 非硬编码验证:移除硬编码字面量,且代码内的常量如
{0,1,2,1005}均不包含任一正确答案。
- 异源验证:采用 Python 的内置