倍数问题
题目描述
【题目描述】
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。
【输入格式】
从标准输入读入数据。
第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。
【输出格式】
输出到标准输出。
输出一行一个整数代表所求的和。
【样例输入】
4 3
1 2 3 4
【样例输出】
9
【样例解释】
选择2、3、4。
【数据约定】
对于 30% 的数据，n <= 100。
对于 60% 的数据，n <= 1000。
对于另外 20% 的数据，K <= 10。
对于 100% 的数据，1 <= n <= 10^5, 1 <= K <= 10^3，给定的 n 个数均不超过 10^8。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
PS：这里就是按照余数，将其分组，然后进行处理，O（NLogN）详细的看代码里面的注释，
有不对得地方或者不懂得地方欢迎评论
package 第二次模拟;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
public class 附加题 {
public static void main(String[] args) throws IOException {
//IO加入快
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] ss=br.readLine().trim().split(" ");
int n=Integer.parseInt(ss[0]);
int K=Integer.parseInt(ss[1]);
ss=br.readLine().trim().split(" ");
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=Integer.parseInt(ss[i]);
}
//进行排序，当然这里如果可以自己写排序的话可能会更快一些
Arrays.sort(a);
int[] mod=Arrays.copyOf(a,n);
Stack<Integer>[] st=new Stack[K];
//数组初始化
init(st);
//我给这里%k是因为我要分为k个栈，因为我要保证三个数的和为k的倍数，这里%k为了分组，把相同余数的分到一起
//例子给的k=3 我要想办法把三个数变成3的倍数，大同小异，就是按照余数进行分组
//从小到大，进行插入，因为是栈，所以最大的在最上面，（后进去的在上面）
for(int i=0;i<n;i++){
mod[i]%=K;
st[mod[i]].add(a[i]);
}
int sum=0;
//如果能整除的数（余数为0）大于2个，那么我先把它变成sum，
if(st[0].size()>2){
Stack<Integer> temp=st[0];
sum=temp.pop()+temp.pop()+temp.pop();
}
int max=sum;
//这里因为要可以%k，那么三个数的和，可能为k，也可能为2k，当前是k的可能，下面是2k的可能
//i j p 就是我要取得三个余数 p+i+j==k(line:47) 所以我可以在这三个余数得数组里面选取最大的
for(int i=0;i<K;i++){
if(st[i].isEmpty())continue;
for(int j=i;j<K;j++){
if(st[j].isEmpty())continue;
int p=K-i-j;//这里保证了我的p+i+j的和为k
if(p>=0&&p<K){
if(st[p].isEmpty())continue;
//当我三个余数相等，就是这个栈得拿出来，然后我要栈顶得三个数
if(i==j&&j==p&&st[i].size()>=3){
Stack<Integer> temp=st[i];
sum=temp.pop()+temp.pop()+temp.pop();
//i和j一样时 取i得两个和p得一个栈顶得值，，下面同理
}else if(i==j&&j!=p&&st[i].size()>=2){
Stack<Integer> temp=st[i];
Stack<Integer> temp1=st[p];
sum=temp.pop()+temp.pop()+temp1.peek();
}else if(i==p&&i!=j&&st[i].size()>=2){
Stack<Integer> temp=st[i];
Stack<Integer> temp1=st[j];
sum=temp.pop()+temp.pop()+temp1.peek();
}else if(j==p&&i!=j&&st[j].size()>=2){
Stack<Integer> temp=st[j];
Stack<Integer> temp1=st[i];
sum=temp.pop()+temp.pop()+temp1.peek();
//当我三个都不相等得时候，我就可以把每个余数相对应得栈中得栈顶取出
}else if(i!=j&&j!=p){
Stack<Integer> temp=st[i];
Stack<Integer> temp1=st[j];
Stack<Integer> temp2=st[p];
sum=temp.peek()+temp1.peek()+temp2.peek();
}
if(sum>max)max=sum;
}
}
}
for(int i=0;i<K;i++){
if(st[i].isEmpty())continue;
for(int j=i;j<K;j++){
if(st[j].isEmpty())continue;
int p=2*K-i-j;
if(p>=0&&p<K){
if(st[p].isEmpty())continue;
if(i==j&&j==p&&st[i].size()>=3){
Stack<Integer> temp=st[i];
sum=temp.pop()+temp.pop()+temp.pop();
}else if(i==j&&j!=p&&st[i].size()>=2){
Stack<Integer> temp=st[i];
Stack<Integer> temp1=st[p];
sum=temp.pop()+temp.pop()+temp1.peek();
}else if(i==p&&i!=j&&st[i].size()>=2){
Stack<Integer> temp=st[i];
Stack<Integer> temp1=st[j];
sum=temp.pop()+temp.pop()+temp1.peek();
}else if(j==p&&i!=j&&st[j].size()>=2){
Stack<Integer> temp=st[j];
Stack<Integer> temp1=st[i];
sum=temp.pop()+temp.pop()+temp1.peek();
}else{
Stack<Integer> temp=st[i];
Stack<Integer> temp1=st[j];
Stack<Integer> temp2=st[p];
sum=temp.peek()+temp1.peek()+temp2.peek();
}
if(sum>max)max=sum;
}
}
}
System.out.println(max);
}
//进行数组初始化
private static void init(Stack<Integer>[] st) {
for(int i=0;i<st.length;i++){
st[i]=new Stack<Integer>();
}
}
}
PS:
这是一个必炸的方法，当时天真的认为dfs，结果。。。还是附上把，下次给自己一个提醒
import java.util.Scanner;
public class MultiplyMax {
static int max = 0;
//深搜递归调用
//解释:sum代表当前找到的数的总和,
//k题目所给,cur代表当前遍历到的数组下标,
//curCount代表当前已经找到的最大数个数
static void dfs(int[] a,int sum,int k,int cur,int curCount) {
//满足题目要求
if( sum%k == 0 && curCount == 3 && max<sum ) {
max = sum;
}
//当前遍历已经到达数组尾部
if( cur == a.length ) return ;
//添加当前a[cur]元素,成为三个数中一个
dfs(a,sum+a[cur],k,cur+1,curCount+1);
//不添加当前a[cur]元素
dfs(a,sum,k,cur+1,curCount);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for( int i=0; i<n; i++ ) {
a[i] = sc.nextInt();
}
//初始情况从数组下标0开始遍历
dfs(a,0,k,0,0);
System.out.println(max);
}
}