题目描述
众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数,希望你从这 n 个数中找到三个数,使得这三个数的和是 K 的倍数,且这个和最大。
数据保证一定有解。
数据范围
1≤ n ≤10^5,
1≤ K ≤10^3,
给定的 n 个数均不超过 108
样例
4 3
1 2 3 4
9
(同余定理 + 贪心)
时间复杂度 $O(k^2)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+5 , M = 1e3+3;
vector<int> vec[M];
int n,k,x , a[N] , ans;
void boli(){ //暴力康康
int posi , posj ,posh , ans = 0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
for(int h=j+1;h<n;h++){
int res = a[i]+a[j]+a[h];
if(res%k==0 && res > ans) { ans = max(ans , res); posi = i; posj = j ; posh = h; }
}
}
}
cout<<ans<<" "<<a[posi]<<" "<<a[posj]<<" "<<a[posh]<<endl;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n,greater<int>());
for(int i=0;i<n;i++){
int mod = a[i]%k;
vec[mod].push_back(a[i]);
if(vec[mod].size()>=3 && (mod*3)%k==0) ans = max(ans , vec[mod][0]+vec[mod][1]+vec[mod][2]);
}
for(int i = 0 ; i < k ; i++){ //枚举第一个数
if(!vec[i].size()) continue;
for(int j = i+1 ; j < k ; j++){ //枚举第二个数
if(!vec[j].size()) continue;
int pos = (k-((i+j)%k)) % k;
if(!vec[pos].size() || (i==j && pos ==j)) continue; //三个已经在上面算过了,
int res = 0;
bool f = (pos==i || pos==j);
if(f && vec[pos].size() < 2) continue;
if(f) res = vec[i][0] + vec[j][0] + vec[pos][1];
else res = vec[i][0] + vec[j][0] + vec[pos][0];
if(res%k==0) ans = max(ans , res);
}
}
cout<<ans<<endl;
return 0;
/*
10 8
100 89 43 40 34 32 20 19 17 9 4
0 : 40 32
1 : 89 17 9
2 : 34
3 : 43 19
4 : 100 20
5 :
6 :
7 :
*/
/*
100 19
1863 353 1022 2011 555 1653 2436 1105 1975 1762 1319 2393 1060
1874 734 1027 690 981 1777 2516 901 2580 855 2984 2467 652 1893
2751 2206 2141 2169 844 2847 1052 2618 2328 1056 2539 142 1232
2669 1166 2369 1473 1653 515 7 762 1910 1392 460 2476 1472 968
785 2553 2554 2632 663 1386 1398 2925 678 2422 1254 2906 2283
151 1679 39 1384 327 1911 2552 337 2858 1212 642 1975 1818 1331
1326 2319 48 2883 291 1222 1817 2641 1284 2953 425 1226 1157
949 681 2435 2997 914 1725
res:8797
*/
}