最大三位数之和 - 算法题解

最大三位数之和 - 算法题解

题目描述

从 N 个正整数中选出 3 个使他们的和在不超过 M 的同时尽可能的大。

输入格式

第一行包含两个正整数 N(3≤N≤10^2), M(10≤M≤300000)。

第二行包括 N 个不大于 10^5 的正整数。

数据保证至少存在 3 个正整数的和不超过 M。

输出格式

输出一行包含可以得到的最大总和。

解题思路

我们可以先将输入的 N 个正整数按照从大到小的顺序排序，然后依次选取前三个数，计算他们的和，如果和小于等于 M 则输出，否则继续选取下一个数。这样可以保证我们选取的三个数的和是最大的。

代码示例 (Python)

N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort(reverse=True)

max_sum = 0
for i in range(3):
    max_sum += nums[i]

print(max_sum)

解释

1. 首先，我们读取输入数据，将 N 和 M 存储到变量中，并将 N 个正整数存储到列表 nums 中。
2. 使用 sort(reverse=True) 将列表 nums 按照从大到小的顺序排序。
3. 初始化最大和 max_sum 为 0。
4. 循环遍历前三个数字，将它们加到 max_sum 中。
5. 最后，输出 max_sum 的值。

时间复杂度

排序的时间复杂度为 O(N log N)，其他操作的时间复杂度为 O(1)，因此总的时间复杂度为 O(N log N)。

空间复杂度

空间复杂度为 O(N)，用于存储输入的 N 个正整数。