2277 问题 B: [蓝桥杯][2018年第九届真题]倍数问题

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

输入
从标准输入读入数据。

第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。
输出
输出到标准输出。
输出一行一个整数代表所求的和。
样例输入
4 3
1 2 3 4
样例输出
9

解题报告：dfs做太慢了，注意到k比1000还小，我透，，那直接把每个余数相等的存下来，枚举两层k最后一层用3*k-i-j %k不就行了，最难的是判断三个数是否相等的情况，考虑细致点应该没问题

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=100010;
int	n,k; 
int a[N];
bool st[N];
int cnt[N];
int	ans=-1e9;
vector<int>vv[1010];
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	cin>>a[i];
	for(int i=0;i<n;i++)
	{
		vv[((a[i])%k)].push_back(a[i]);
	}
	for(int i=0;i<k;i++)
	{
	if(!vv[i].size())
	continue;
	sort(vv[i].begin(),vv[i].end());
	reverse(vv[i].begin(),vv[i].end());
	}
	for(int i=0;i<k;i++){
		if(!vv[i].size())
		continue;
	for(int j=0;j<k;j++)
	{
		if(!vv[j].size())
		continue;
	if(vv[(3*k-i-j)%k].size())
	{
		int t=(3*k-i-j)%k;
		if(i==j&&j==t)
		{
			if(vv[0].size()<3)
			continue;
			else
			ans=max(ans,vv[i][0]+vv[i][1]+vv[i][2]);
		}
		else if(i==j||j==t||i==t) 
		{
			if(i==j)
			{
				if(vv[i].size()<2)
				continue;
				ans=max(ans,vv[i][0]+vv[i][1]+vv[t][0]);
			}
			if(i==t)
			{
				if(vv[i].size()<2)
				continue;
				ans=max(ans,vv[i][0]+vv[i][1]+vv[j][0]);
			}
			if(j==t)
			{
				if(vv[j].size()<2)
				continue;
				ans=max(ans,vv[j][0]+vv[j][1]+vv[i][0]);
			}
		}
		else 
		{
		ans=max(ans,vv[i][0]+vv[j][0]+vv[t][0]);
		}
	}
	} 
					}
	cout<<ans<<endl;
    return 0;
}