题目描述

直接暴力枚举三数和的情况
枚举n肯定不行 K只有1000 考虑枚举余数情况
（纯小白做题）
思路：
对数组排序，并装入余数桶中 保证每个桶是从大到小
枚举i+j+k%K==0的情况 都是0~K-1 因为存在余数相等满足的情况
优化k 因为i j皆小于K所以对与k的情况只有i+j==0 那么k=0 否则k满足的情况只有K-(i+j)%K

算法

(暴力枚举) $O(K^2)$

C++ 代码

typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
const int linf=1e9;
const int logN=21;
int n,m,K;

int t;
int ans=0;
int b[N];
void solve(){
    cin>>n>>K;
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(b+1,b+1+n,greater<int>());
    vector<int> a[K+10];

    for(int i=1;i<=n;i++){
        a[b[i]%K].push_back(b[i]);
    }

    for(int i=0;i<K;i++){
        for(int j=0;j<K;j++){
            int k;
            if((i+j)%K==0){
                k=0;
            }
            else{
                k=K-(i+j)%K;
            }
            if(i!=j&&i!=k&&j!=k){
                if(a[i].size()>=1&&a[j].size()>=1&&a[k].size()>=1) ans=max(ans,a[i][0]+a[j][0]+a[k][0]);
            }
            else if(i==j&&j!=k){
                if(a[i].size()>=2&&a[k].size()>=1) ans=max(ans,a[i][0]+a[j][1]+a[k][0]);
            }
            else if(i==k&&i!=j){
                if(a[i].size()>=2&&a[j].size()>=1) ans=max(ans,a[i][0]+a[j][0]+a[k][1]);
            }
            else if(j==k&&i!=j){
                if(a[j].size()>=2&&a[i].size()>=1) ans=max(ans,a[i][0]+a[j][0]+a[k][1]);
            }
            else if(i==k&&i==j){
                if(a[i].size()>=3) ans=max(ans,a[i][0]+a[j][1]+a[k][2]);
            }
        }
    }

    cout<<ans<<endl;
    // for(int i=1;i<=n-2;i++){
    //     for(int j=i+1;j<=n-1;j++){
    //         for(int k=j+1;k<=n;k++){
    //             if((a[i]+a[j]+a[k])%K==0){
    //                 ans=max(ans,a[i]+a[j]+a[k]);

    //             }
    //         }
    //     }
    // }
    // cout<<ans<<endl;
}

int main()
{

    t=1;
    while (t -- ){
        solve();
    }

    return 0;

}