题目描述
众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。
现在小葱给了你 n
个数,希望你从这 n
个数中找到三个数,使得这三个数的和是 K
的倍数,且这个和最大。
数据保证一定有解。
输入格式
第一行包括 2 个正整数 n, K
。
第二行 n
个正整数,代表给定的 n
个数。
输出格式
输出一行一个整数代表所求的和。
数据范围
1≤n≤105
,
1≤K≤103
,
给定的 n
个数均不超过 108
算法
(暴力枚举) $O(k^2)$
如果直接暴力枚举的话,就是从n个数选3个进行验证,复杂度会是O(n^3),n最大为100000,会大大超时,
但思考后发现这个K只有1000,于是想到用K进行暴力枚举,只需要用一个数组d[i]存储每个余数为i的最大数,
题目中要的是三个数和的最大值,所以只需要保存几个最大值即可
因为根据同余定理,如果(a%k + b%k + c%k) % k ==0,则a + b + c 一定是k的整数倍,所以,只需存储每个余数
对应的最大值即可(注意这里存储的不是三个数的和,而是单纯的一个数,就是n个数里面的一个)
这样还有一个问题,就是如果同一个余数只能用一次,就是不能枚举到相同的数,如果最后答案里面三个数都能
分别被K整除,就无法枚举到,于是就想到了用d[i][j]二维数组存储,d[i][j]的含义是余数为i的第j大的数,
比如说d[2][3]就表示余数为2,并且在所有余数为2的数里面第三大的数,d[2][1]就是余数为2的数里面最大的数。
这样就避免了一个余数只能用一次的情况,而是可以用多次,但是还会出现一个问题,就是重复问题,因为一个数
只能被选一次,于是还要做到去重,就是选到了某个数后就不能再选了,因为这n个数里面可能有多个重复的,所以
不能用数值来判断是否选过。因为每个数组对应的值都有唯一一个地址,于是就想到了用地址作为判断是否选过的
依据,用int* vis指针来存储每个选过的值的地址,这样就完成了去重。
但是还有一个问题,就是如果全都枚举一遍,这样的话复杂度就是 3000 * 3000 * 3000 ,也会超时,于是就想,
能不能只枚举两层,发现还真可以,因为如果已经知道了前两个余数a,b,那么第三个余数是可以计算出的,结果是
(k- a - b + k)%k ,这样的话,只需要枚举前两个数的余数,第三个余数直接计算即可得出,复杂度大概是3000 * 3000 * 3 大概是两千七百万的复杂度,小于1亿,可以通过。理论可行,下面实现代码。
时间复杂度 千万级别
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int d[1005][4] = {{0,0,0,0}};//记录前三个大的数
int w[100010];//记录每个数
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);//提高cin cout输入输出速度,这个题不需要,因为当时刚学,就默写了一遍
int n,k;
cin >> n >> k;
for(int i = 1;i<=n;i++){//读入n个数,并且在这里面维护d数组
cin >> w[i];
int t = w[i] % k;
if(d[t][1] < w[i]){//如果新出现的这个数比之前保存的最大的还要大
d[t][3] = d[t][2];//淘汰最后一个
d[t][2] = d[t][1];//后面顺位更新
d[t][1] = w[i];
}
else if(d[t][2] < w[i]){//比第二个大,比第一个小
d[t][3] = d[t][2];
d[t][2] = w[i];
}
else if(d[t][3] < w[i]){//比第三个大,比第二个小
d[t][3] = w[i];
}
}
int sum = 0;//记录结果
for(int i = 0;i<=k-1;i++){
for(int i1 = 1;i1<=3;i1++){
if(d[i][i1] == 0){//没有这个值,因为每个数都是正整数,如果是0表示没有这个值
continue;
}
int*vis1 = &d[i][i1];//用vis1存储选择的是哪个数
for(int j = 0;j<=k-1;j++){
for(int i2 = 1;i2<=3;i2++){
if(d[j][i2] == 0){
continue;
}
int*vis2 = &d[j][i2];
if(vis2 == vis1){//如果第二个选择的数和第一个选择的数一样,出现重复,则continue
continue;
}
int t = (k - i - j + k) % k;//计算第三个数的余数
for(int i3 = 1;i3 <= 3;i3++){//这里需要看余数为t的三个数。
if(d[t][i3] == 0){
continue;
}
int*vis3 = &d[t][i3];
if(vis3 == vis2 || vis3 == vis1){//去重
continue;
}
if(sum < (d[i][i1] + d[j][i2] + d[t][i3])){//如果出现了更大的符合条件的值,就更新
sum = d[i][i1] + d[j][i2] + d[t][i3];
}
}
}
}
}
}
cout << sum;
return 0;
}
欢迎各位批评指正。