P4706 寻找最大和（入门）

解题思路

有 n 个数，要从中挑出 3 个数，让它们的和不超过 m，并且让这个和尽量大。如果怎么挑都会超过 m，就输出 0。

n 的规模不大，所以可以暴力枚举：用三重循环把所有的"选 3 个数"的组合都试一遍。第一层循环定第一个数 i，第二层定第二个数 j（从 i 后面开始），第三层定第三个数 k（从 j 后面开始），这样每个组合恰好被算一次，不会重复也不会漏。让 j 从 i+1 开始、k 从 j+1 开始，是为了保证 i、j、k 互不相同，并且同一个组合不会被重复计算。比如选了 (5,6,7)，就不会再选 (6,5,7)，因为第二层永远取的是后面的数。

每试一个组合，算出 s = a[i]+a[j]+a[k]。如果 s ≤ m，说明这个组合合格；再和之前找到的最好答案比较，如果更大就更新。循环结束后，ans 里存的就是不超过 m 的最大和。如果一次都没更新，ans 保持初始值 0，正好符合"没有则输出 0"的要求。

举个例子：5 个数 5 6 7 8 9，m=21。试组合：5+6+7=18，5+6+8=19，5+7+9=21……最大合格的和是 21（5+7+9 或 6+7+8），输出 21。

边界情况：如果 n 小于 3，根本选不出 3 个数，应该输出 0；三个数相加可能超过 int 的范围，所以用 long long 存和。

参考代码

// 寻找最大和：从 n 个数中选 3 个，和不超过 m 时求最大和
#include <iostream>
using namespace std;

int a[1005];

int main() {
    int n;
    long long m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    long long ans = 0; // 找不到符合条件的三数就输出 0
    // 三重循环枚举三个数
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                long long s = a[i] + a[j] + a[k];
                if (s <= m && s > ans) ans = s; // 更新最优答案
            }
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

三重循环，每层最多 n 次，时间复杂度 O(n³)。在 n 不大的时候（几百以内）完全没问题。空间 O(n) 用来存这 n 个数。