P4389 不与最大数相同的数字之和（基础）

解题思路

输入 n 个数，要算出"所有不等于最大值的数"加起来的和。注意是"不等于最大值"——如果最大值出现了很多次，这些最大值一个都不能加进去。

那我们就分两步走： 第一步，先扫一遍数组，找出最大值 mx； 第二步，再扫一遍数组，把所有不等于 mx 的数累加进答案 ans。

为什么要分两步？因为必须先知道最大值是多少，才能判断每个数要不要加。所以要么用数组把数都存下来，要么扫两遍。

拿样例 1 2 3 来说，最大值是 3，不等于 3 的有 1 和 2，它们的和是 3，正好是答案。

边界情况：数字允许是负数（范围是 -10000 到 10000），所以 mx 的初始值要设成一个比所有数都小的数，比如 -20000，否则找最大值会出错。最大值出现多次时，比如 5 5 1，最大值 5 出现两次，两个 5 都不加，答案就是 1。n 个数的和可能比较大，用 long long 存答案更保险。

参考代码

// 程序用途：输出n个数中所有不等于最大数的数字之和
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[105] = {0};                 // 数组存下n个数（n最大100）
    int mx = -20000;                  // mx记录最大值，先设成可能的最小值
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > mx) mx = a[i];     // 打擂台找出最大值
    }
    long long ans = 0;                // 用long long防止和太大
    for (int i = 0; i < n; i++) {
        if (a[i] != mx) ans += a[i];  // 不等于最大数的才累加
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

一共扫两遍数组，每遍处理 n 个数，时间复杂度是 O(n)；需要用数组把所有数存下来，额外空间复杂度是 O(n)。