标题:倍数问题html
【题目描述】
众所周知,小葱同窗擅长计算,尤为擅长计算一个数是不是另一个数的倍数。但小葱只擅长两个数的状况,当有不少个数以后就会比较苦恼。如今小葱给了你 n 个数,但愿你从这 n 个数中找到三个数,使得这三个数的和是 K 的倍数,且这个和最大。数据保证必定有解。ios
【输入格式】
从标准输入读入数据。函数
第一行包括 2 个正整数 n, K。
第二行 n 个正整数,表明给定的 n 个数。post
【输出格式】
输出到标准输出。
输出一行一个整数表明所求的和。spa
【样例入】
4 3
1 2 3 4操作系统
【样例输出】
9code
【样例解释】
选择二、三、4。htm
【数据约定】
对于 30% 的数据,n <= 100。
对于 60% 的数据,n <= 1000。
对于另外 20% 的数据,K <= 10。
对于 100% 的数据,1 <= n <= 10^5, 1 <= K <= 10^3,给定的 n 个数均不超过 10^8。blog
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms内存
请严格按要求输出,不要多此一举地打印相似:“请您输入...” 的多余内容。
注意:
main函数须要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操做系统的特殊函数。
全部依赖的函数必须明确地在源文件中 #include <xxx>
不能经过工程设置而省略经常使用头文件。
提交程序时,注意选择所指望的语言类型和编译器类型。
思路: 首先将这n个数从大到小排好序,而后依次枚举3个组合数,判断是否符合条件。因为是从大到小枚举,因此第一次出现的结果必定是最终结果。
如何利用dfs枚举组合数请参考:https://www.cnblogs.com/FengZeng666/p/10496287.html
1 #include<iostream> 2 #include<string> 3 #include<queue> 4 #include<set> 5 #include<cstring> 6 #include<cmath> 7 #include<algorithm> 8 #include<stdio.h> 9 10 #define MAX 1000000000 11 12 using namespace std; 13 14 int n, K; 15 int a[100010]; 16 int b[4]; 17 int flag = 0; 18 19 void dfs(int a[], int n, int step) // a中有n个数(已经从大到小排好序),在里面取3个数,存放到b[4]中(b[0]不使用)。 20 { 21 if (flag == 1) 22 return; 23 24 if (step == 4) 25 { 26 int sum = b[1] + b[2] + b[3]; 27 if (sum % K == 0) 28 { 29 flag = 1; 30 cout << sum << endl; // 由于是从大到小枚举组合数,因此第一个sum必定是最大的 31 } 32 return; 33 } 34 35 for (int i = 1; i <= n; ++i) 36 { 37 if (a[i] < a[step - 1]) 38 { 39 b[step] = a[i]; 40 dfs(a, n, step + 1); 41 } 42 } 43 } 44 45 int main() 46 { 47 cin >> n >> K; 48 a[0] = MAX; // 做为第一次比较时的"哨兵" 49 for (int i = 1; i <= n; ++i) 50 cin >> a[i]; 51 52 sort(a + 1, a + n + 1); //从小到大排好序 53 reverse(a + 1, a + n + 1); //变为从大到小 54 55 56 dfs(a, n, 1); 57 58 59 return 0; 60 }