最大三数和问题

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例内容：

输入样例 #1 5 20 4 7 9 12 16

输出样例 #1 19

输入样例 #2 6 50 10 20 30 40 50 60

输出样例 #2 120

说明

对于样例#1，可以选择4、7、9，它们的和为20，是满足条件的最大总和。

对于样例#2，可以选择50、40、30，它们的和为120，是满足条件的最大总和。

解题思路

本题可以使用贪心算法来解决。首先对所有数字进行排序，然后从最大的数字开始选择，如果当前数字加上前两个数字的和小于等于'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(N - 2):
    if nums[i] + nums[i + 1] + nums[i + 2] <= M:
        max_sum = nums[i] + nums[i + 1] + nums[i + 2]
        break

print(max_sum)

代码示例 (C++)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int nums[N];
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + N, greater<int>());

    int max_sum = 0;
    for (int i = 0; i < N - 2; i++) {
        if (nums[i] + nums[i + 1] + nums[i + 2] <= M) {
            max_sum = nums[i] + nums[i + 1] + nums[i + 2];
            break;
        }
    }
    cout << max_sum << endl;
    return 0;
}

代码示例 (Java)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        Arrays.sort(nums);
        int maxSum = 0;
        for (int i = N - 1; i >= 2; i--) {
            if (nums[i] + nums[i - 1] + nums[i - 2] <= M) {
                maxSum = nums[i] + nums[i - 1] + nums[i - 2];
                break;
            }
        }
        System.out.println(maxSum);
    }
}

总结

本题的解题思路非常简单，只需要对所有数字进行排序，然后从最大的数字开始选择即可。贪心算法的应用让代码更加简洁高效。希望这份题解能够帮助你更好地理解和解决这道算法题。