题目描述
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n个数，希望你从这 n个数中找到三个数，使得这三个数的和是 K的倍数，且这个和最大。数据保证一定有解。
输入描述
第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n个数。
输出描述
输出一行一个整数代表所求的和。
输入输出样例
示例
输入
4 3
1 2 3 4
输出
9
想法：
-
通过列出题目给出的数学表达式，可知我们可以通过每个数的余数来进行和的比较，这样时间复杂度为k*k
-
首先进行排序，然后创建vector容器，将余数相同的作为下标，将其值push_back到容器中，并且其值是按照从小到大顺序。
-
对第一个和第二个余数进行枚举，第三个符合条件的余数可以通过表达式的推导
-
先看数据范围，n最大100000,k=1000,如果以n思考解题思路枚举三数之和至少是n*n。明显超时，但是如果从k来看，有没有方法可以做到k。我们要求的是k的倍数。 k的倍数有什么性质？ 显然有k的倍数m,m%k==0;
-
m=a+b+c,m%k=(a+b+c)%k 根据同余定理有[(a%k)+(b%k)+(c%k)]%k=0; 那么我们只需要找到某些余数满足相加后再模k即可，同余数的只需要考虑最大值。 所以排个序，把相同余数的放在一起一起。保证后面的数大于前面的数(先排序的原因)。
-
接下来就是枚举前两个余数，最后一个余数自然就是( m-（i+j）%m)%m。 之后就是检查3个余数是否相同，是否有这么多个余数。
-
#include<bits/stdc++.h>
using namespace std;
int a[100010];
vector<int> mod[1010];
int get(int i,int j,int m){
int size1 = mod[i].size();
int size2 = mod[j].size();
int size3 = mod[m].size();
if(i == j&&i == m){
if(size1 >= 3){
return mod[i][size1-1] + mod[i][size1-2] + mod[i][size1 -3];
}
}
else if(i == j&&i != m){
if(size1 >=2&&size3 >= 1){
return mod[i][size1-1] + mod[i][size1-2] + mod[m][size3 -1];
}
}
else if(i != j&&i == m){
if(size1 >=2&&size2 >= 1){
return mod[i][size1-1] + mod[j][size2-1] + mod[i][size1 -2];
}
}
else if(i != j&&m == j){
if(size1 >= 1&&size2 >= 2){
return mod[i][size1-1] + mod[j][size2-1] + mod[m][size2 -2];
}
}
else if(i !=j&&i != m&&m != j){
if(size1 >= 1&&size2 >= 1&&size3 >=1){
return mod[i][size1-1] + mod[j][size2-1] + mod[m][size3 -1];
}
}
return 0;
}
int main(){
int n,k;
cin>>n>>k;
for(int i = 0;i < n;++i){
cin >> a[i];
}
sort(a,a+n);
for(int i = 0;i < n;++i){
mod[a[i]%k].push_back(a[i]);
}
int res = 0;
for(int i = 0;i < k;++i){
for(int j = i;j < k;++j){
res = max(res, get(i, j, (k - ((i + j) % k))%k));
}
}
cout << res <<endl;
return 0;
}