申题描述之一帮之数的正数中选出3个使得他们的和在不超过M的同时尽可能的大。
输入格式
第一行包含两个正数N(3≤N≤102),M(10≤M≤300000)。
第二行包含N个不大于105的正数。
数据保证至少存在3个正数的和不超过M;。
输出格式
输出一行包含可以获得的最大总和。
解法一&#xuff1a;指名所有可能的三个数的组合、求出他们的和、如果和不超过M;、更新最大总和。
```cpp#include #include #include using namespace std;
int main() { int N, M; cin >> N >> M; vector nums(N); for (int i = 0; i < N; i++) { cin >> nums[i]; } int maxSum = 0; for (int i = 0; i < N-2; i++) { for (int j = i+1; j < N-1; j++) { for (int k = j+1; k < N; k++) { int sum = nums[i] + nums[j] + nums[k]; if (sum <= M) { maxSum = max(maxSum, sum); } } } } cout << maxSum << endl; return 0;}
解法二&#uff1a;先对数组进行排序、然后从数组的最大值开始指名、假设最大值为x;、那么剩余的两个数的和不超过M-x;、找到最近于M-x;的两个数的和、然后和x的和就是目前的最大总和。
```cpp#include #include #include using namespace std;
int main() { int N, M; cin >> N >> M; vector nums(N); for (int i = 0; i < N; i++) { cin >> nums[i]; } sort(nums.begin(), nums.end()); int maxSum = 0; for (int i = N-1; i >= 2; i--) { int target = M - nums[i]; int left = 0, right = i-1; while (left < right) { int sum = nums[left] + nums[right]; if (sum <= target) { maxSum = max(maxSum, sum + nums[i]); left++; } else { right--; } } } cout << maxSum << endl; return 0;}

