【例5.5】最大数位置

GitHub跳转原题关系图返回列表

遍历打擂台寻找最大值,需要使用 `long long` 防止大整数溢出,并注意记录第一次出现的位置。

OJ: roj

题目 ID: 5040

难度:入门

标签:数组模拟

创建: 2026-10-08 23:13

更新: 2026-10-08 23:13

形式化题目

给定一个长度为 nn 的正整数序列 a1,a2,…,ana_1, a_2, \dots, a_n,其中 1≤n≤10001 \le n \le 1000,且对于任意 1≤i≤n1 \le i \le n,均有 ai≤232−1a_i \le 2^{32}-1。 求出该序列中最大数所在的位置下标(采用 1-based 编号,即第 1 个元素位置为 1)。如果有多个相同的最大数值,输出它们之中第一次出现的位置(即最小的下标)。

正解

思路

本题的本质是一个打擂台求最大值及对应位置的题目。我们需要从前往后遍历序列,用变量记录当前遇到的最大数值的下标 max_pos(和其对应的值 max_val)。 每遇到一个元素 xx(其下标为 ii),如果 x>max_valx > max\_val,则更新 max_pos = i。因为只有在严格大于时才更新,所以如果遇到相同的最大值,不会覆盖第一次记录的位置,这天然满足了题目「并列时取第一次出现位置」的隐含需求。

这道题的核心陷阱在于数值范围: 题面说明“每个数在 232−12^{32}-1 之内”。而 232−1=42949672952^{32}-1 = 4294967295。 在 C++ 中,普通的带符号 int 类型能表示的最大正整数为 231−1=21474836472^{31}-1 = 2147483647。 由于数据点中包含超过 INT_MAX 的值(如 42949672954294967295),如果使用普通的 cin >> int 来读取,由于读入的值超出了 int 的上界,cin 不会发生“回绕成负数”的现象,而是会将该变量钳位为 INT_MAX(21474836472147483647),并锁死输入流的 failbit。这会导致此后所有的读入全部失败(读入值为 0),从而把最大值错误地“冻结”在已经成功读入的前缀里,结果与真实值无关,必然算错。 (如果是 scanf("%d") 或对 long long 读入后强制转 (int),则会发生真实的截断回绕现象,例如 42949672954294967295 会回绕变成 −1-1)。 因此,在 C++ 实现中,我们必须使用范围更大的数据类型,即 long long。相对而言,Python 支持任意精度的大整数,因此使用 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()
cpp
/**
 * 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;
}

复杂度

  • 时间复杂度:O(n)\mathcal{O}(n)。我们需要遍历 nn 个数进行比较,每次比较的操作时间是常数的。
  • 空间复杂度:O(n)\mathcal{O}(n)。本题在代码实现中,开辟了数组 a[1..n] 来储存输入的数据,空间消耗随数据规模线性增长。

总结

  • 数值范围与类型(本题核心):
    • 本题中数据的最大值达到了 4294967295=232−14294967295 = 2^{32}-1。实测显示数据点 2、5、6、8、9、10 均含有超过 INT_MAX 的值。
    • cin >> int 的行为与溢出危害:在处理超限数据时,cin >> int 不会像 scanf 或强转那样回绕成负数,而是会把值钳位在 INT_MAX 并且置位 failbit。一旦置位,后续所有的读入均会被忽略。实验表明,如果本题把变量类型换成 int,会导致 4/104/10 个测试点直接错误(输出的位置错误地停留在由于报错而停止读取的前面部分)。
    • 为什么不用 unsigned int?:虽然 unsigned int 的上限刚好是 232−12^{32}-1,但在打擂台算法中,我们通常需要一个初值。如果沿用习惯的无符号负一初值 max_val = (unsigned)(-1),其值等于 42949672954294967295 —— 恰好等于题面上限。这会导致没有任何一个元素能大于这个哨兵值,导致 10/1010/10 全错(全输出 −1-1)。直接用数组第一个元素作初值可以规避,但为了稳妥且遵守项目规范,统一使用 long long 处理超过 int 的数据更加安全。
  • 并列最大值的处理:题面只规定了输出“最大数所在位置”,但未对多个相同的最大值做显式说明。通过实测验证:
    • 在全相等的测试点(如 p9,1000 个 232−12^{32}-1),输出是 1。
    • 在最大值出现多次的测试点(如 p7,最大值出现 24 次,最先出现在位置 116),输出为 116。
    • 结论:并列时应当输出第一次出现的位置。我们在条件判断中使用严格大于 (>) 天然契合这一逻辑。
  • 1-based 编号与末尾位置验证:
    • 题面明确提到“存放在数组 a[1]a[1] 至 a[n]a[n] 中”,因此要遵循 1-based 索引。样例输出以及最大值出现在末尾的测试点(如 p10 的最大值恰好在第 1000 位,正确输出了 1000)都证实了输出位置不应减 1。
  • 验证强度:
    • 异源验证:采用 Python 的内置 max() 加 index() 算法与 C++ 的单遍流式打擂台算法对比,对 373 组穷举测试点(n≤5n \le 5, 取值 {1,2,3}\{1,2,3\} 加上边界点)实现了 0 分歧。
    • 非硬编码验证:移除硬编码字面量,且代码内的常量如 {0,1,2,1005} 均不包含任一正确答案。