解题思路

题目要求“除去最大数之后，剩下所有数字的和”。

注意：“除去最大数”指的是所有等于最大值的数都不算。比如输入 1 2 3，最大值是 3，只去掉一个 3，剩下的 1 和 2 加起来等于 3；如果输入 1 3 3 2，最大值是 3，两个 3 都要去掉，剩下 1 和 2，答案是 3。

做法分两步：

1. 把 n 个数读进数组 a，读的过程中顺便找出最大值 mx（用“打擂台”的方法，遇到更大的数就更新）；
2. 再遍历一遍数组，把所有不等于 mx 的数累加起来。

因为每个数的绝对值可能到 1000000，和有可能很大，所以用 long long 来存和，更保险。

参考代码

// P4445 不与最大数相同的数字之和：先找最大值，再累加不等于它的数
#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;               // 数的个数
    int a[105];
    int mx = -2000000000;   // 最大值，先设成很小
    for (int i = 0; i < N; i++) {
        cin >> a[i];        // 读入每个数
        if (a[i] > mx) mx = a[i];  // 顺便找出最大值
    }
    long long sum = 0;      // 用 long long 存和，更保险
    for (int i = 0; i < N; i++) {
        if (a[i] != mx) sum += a[i];  // 只加“不等于最大值”的数
    }
    cout << sum << endl;
    return 0;
}

复杂度分析

设有 n 个数。

• 时间：第一遍找最大值，第二遍累加，共两遍循环，时间复杂度是 O(n)。
• 空间：需要一个能装 n 个数的数组，空间复杂度是 O(n)。