倍数问题
众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。但小葱 只擅长两个数的情况,当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数,希望你 从这 n 个数中找到三个数,使得这三个数的和是 K 的倍数,且这个和最大。数据保证一 定有解。
输入
从标准输入读入数据。 第一行包括 2 个正整数 n,K。
第二行 n 个正整数,代表给定的n 个数。
输出
输出到标准输出。 输出一行一个整数代表所求的和。
样例
输入
4 3
1 2 3 4
输出
9
数据约定
对于 30% 的数据,n <= 100。
对于 60% 的数据,n <= 1000。
对于另外 20% 的数据,K <= 10。
对于 100% 的数据,1 <= n <= 105, 1 <= K <= 103,给定的 n 个数均不超过 108。
数论小知识
当三个数 v1, v2, v3 的和为 K 的倍数时
(v1+v2+v3)%K=0
利用上面数论的知识,我们要创建一个二维数组 group 存储数据。存储关系:余数与数据。
eg:假如我们要存储一个数 5,K 为 4。
那么这个数将会存储在 group[5%4][0] = 5
特殊情况分析:
①、可能取相同余数的情况,所以我们要对每个余数对应的数据进行排序,使得每次取的数都是最大的。
②、题目仅要取三个数,所以我们只要维护每个余数对应前三大的数据。
eg:1 3 4 5 6 那么前三大就是 6 5 4。
AC代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, k;
int group[1000][3];
ll ans=0;
int main(){
cin>>n>>k;
memset(group, 0, sizeof(group));
for(int i=0; i<n; i++){
int x;
cin>>x;
int re = x % k;
if(x > group[re][0]){
group[re][2] = group[re][1];
group[re][1] = group[re][0];
group[re][0] = x;
}
else if(x > group[re][1]){
group[re][2] = group[re][1];
group[re][1] = x;
}
else if(x > group[re][2]){
group[re][2] = x;
}
}
int v1, v2, v3;
for(int i=0; i<k; i++){
v1 = group[i][0];
if(v1!=0){
for(int j=i; j<k; j++){
if(i==j)
v2 = group[j][1];
else
v2 = group[j][0];
if(v2!=0){
int z = (k-(i+j)%k)%k;
if(i!=j){
if(z!=j&&z!=i)
v3 = group[z][0];
else if(z==j)
v3 = group[j][1];
else if(z==i)
v3 = group[i][1];
}
else{
if(z==i)
v3 = group[z][2];
else
v3 = group[z][0];
}
if(v3!=0)
ans = max((ll)v1+v2+v3, ans);
}
}
}
}
cout<<ans;
return 0;
}
总结
这道题说难也不难,考察数论基础以及如何实现题目要求。
简单的东西一定要掌握好,基础由为重要。
如果对你有帮助,请给我个赞吧:)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)