第九届蓝桥杯Java A组第九题倍数问题题解

标题：倍数问题

【题目描述】
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 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。
 

这道题给了三个条件，如下：

1. 从数组中寻找三个数；
2. 找到的数的和是k的倍数；
3. 找到的数的和最大；

因为题目要求很明确，n,k以及数组元素均为正整数，所以定义数据类型时int就可以了，另外，根据以上压缩出来的三个条件，我相信绝大部分同学应该都能想到了深搜算法了，对的，这道题用深搜尽可以解决了，而且很快哦，以下详见我的代码，有误之处还望指正。

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);
	}
}

上述代码简要解释一下：

主要是dfs函数，里面包含5个变量，数组a,输入的k,所求的sum,当前遍历的数组下标cur以及已经找到的元素个数curCount,先进行条件判断，然后对插入a[cur]与不插入a[cur]两种情况分别迭代，然后就可以求出最大值了。

本文参考https://blog.csdn.net/qq_39445165/article/details/88116313。