题目

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数
使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。

输入
4 3
1 2 3 4

输出
9

思路

嵌套循环，从后面开始寻找，关键是剪枝否则运算超时

代码

#include<iostream>
#include <algorithm>
using namespace std;
int main()
{int n,m;int maxs = 0;cin>>n>>m;int s[n];for(int i = 0;i < n;i++){cin>>s[i];}sort(s,s+n);for(int i = n-1;i >= 2;i--){int j = i-1,k = j-1;if(s[i]+s[j]+s[k] < maxs) break;for(int j = i-1;j >= 1;j--){int k = j-1;if(s[i]+s[j]+s[k] < maxs) break;for(int k = j-1;k >= 0;k--){int sum = s[i]+s[j]+s[k];if(sum%m == 0){if(sum > maxs) maxs = sum;if(sum<maxs) break;}}}}cout<<maxs;return 0;
}

总结

• 关键是从后开始和剪枝来提高效率