【蓝桥杯】倍数问题

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。
输入格式
　　从标准输入读入数据。

第一行包括 2 个正整数 n, K。
　　第二行 n 个正整数，代表给定的 n 个数。
输出格式
　　输出到标准输出。
　　输出一行一个整数代表所求的和。
样例入

4 3
1 2 3 4

样例输出

9

样例说明
　　选择2、3、4。
数据约定
　　对于 30% 的数据， n < = 100 n <= 100 n<=100。
　　对于 60% 的数据， n   < = 1000 n <= 1000 n <=1000。
　　对于另外 20% 的数据， K   < = 10 K <= 10 K <=10。
　　对于 100% 的数据， 1 < = n   < = 1 0 5 ,   1 < = K   < = 1 0 3 1 <= n <= 10^5, 1 <= K <= 10^3 1<=n <=105, 1<=K <=103，给定的 n 个数均不超过 1 0 8 10^8 108。

暴力+优化纯粹的三重循环肯定是过不了的，所以需要优化，不过还是暴力的板子优化暴力法的几个方面：减少循环层数；二分；缩小搜索范围；做一些预处理，以空间换时间。这道题中可以先做一些预处理，用空间换时间，然后以此来减少循环次数，做到优化，其实从后往前看的话，这道题在做一方面优化的同时，也一起做了其他方面的优化，比如还缩小了搜索范围。这道题是求三个数的和是某个数的倍数，而不是等于那个数，那就要用到取模方面的知识了根据题意，我们要找 a , b , c a,b,c a,b,c 使得： ( a + b + c )   m o d   k = 0 (a+b+c) mod k=0 (a+b+c) mod k=0而由模运算的知识可知，上面的式子等价于： ( a   m o d   k + b   m o d   k + c   m o d   k )   m o d   k = 0 (a mod k+b mod k+c mod k) mod k=0 (a mod k+b mod k+c mod k) mod k=0这样便可以减少一重循环：利用 a a a 和 b b b 将 c c c 确定下来，就可以从三重循环降到二重循环做一个预处理，把输入的 n n n 个数按照余数分类，余数为0的放在一个集合中，为1的放在一个集合中……，这个过程可以用一个二维数组实现，而且还可以加一个限制条件，即我们只需要3个数的和，所以每个余数的集合里面维护三个数即可，并且要这些和最大，那么就维护最大的三个数令 r 1 = a   m o d   k r_1=a mod k r1​=a mod k； r 2 = b   m o d   k r_2=b mod k r2​=b mod k； r 3 = c   m o d   k r_3=c mod k r3​=c mod k，如果 r 1 + r 2 + r 3 r_1+r_2+r_3 r1​+r2​+r3​ 是 k k k 的倍数的话，那么就是符合题意的我们知道： r 1 , r 2 , r 3 < k r_1,r_2,r_3如果 r 1 = r 2 = r 3 r_1=r_2=r_3 r1​=r2​=r3​，说明 a , b , c a,b,c a,b,c 同余，则答案更新为余数为 r 1 r_1 r1​ 的那三个数(直接访问预处理数组即可)如果 r 1 = r 2 ≠ r 3 r_1=r_2 not=r_3 r1​=r2​​=r3​，说明 a , b a,b a,b 同余，则答案更新为余数为 r 1 r_1 r1​ 的前两个数与余数为 r 3 r_3 r3​ 的第一个数之和如果 r 1 = r 3 ≠ r 2 r_1=r_3 not=r_2 r1​=r3​​=r2​，说明 a , c a,c a,c 同余，则答案更新为余数为 r 1 r_1 r1​ 的前两个数与余数为 r 2 r_2 r2​ 的第一个数之和如果 r 2 = r 3 ≠ r 1 r_2=r_3 not=r_1 r2​=r3​​=r1​，说明 c , b c,b c,b 同余，则答案更新为余数为 r 2 r_2 r2​ 的前两个数与余数为 r 1 r_1 r1​ 的第一个数之和如果 r 1 ≠ r 2 ≠ r 3 r_1not=r_2 not=r_3 r1​​=r2​​=r3​，说明 a , b , c a,b,c a,b,c 两两不同余，则答案更新为余数为 r 1 r_1 r1​ 的第一个数与余数为 r 2 r_2 r2​ 的第一个数与余数为 r 3 r_3 r3​ 的第一个数之和 然后取最大值，输出即可这样就只对 k k k 规模的数组做了二重循环，由题可知 k < 1 0 3 k<10^3 k<103，所以方案是可行的，预处理时维护前三大的数可以用朴素的“插入排序”即可，由于只有3个数进行排序，是 O ( 1 ) O(1) O(1) 复杂度，所以预处理的总复杂度是 O ( n ) O(n) O(n) 的，所以最后的复杂度是 O ( k 2 ) O(k^2) O(k2)，而 k < 1 0 3 k<10^3 k<103，所以不会超时 代码如下

C++用多了，复习一下C语言

#include 

int max(int a, int b) { return a > b ? a : b; }

int n, k;
int a[1001][4];

void solve() {
    scanf("%d%d", &n, &k);
    int i = 0, j = 0, t = 0, d = 0;
    while (n--) {
        scanf("%d", &t);
        d = t % k;
        //一个朴素的插入排序
        for (i = 1; i <= 3; i++) {
            if (t > a[d][i]) {
                for (j = 3; j > i; j--) {
                    a[d][j] = a[d][j - 1];
                }
                a[d][i] = t;
                a[d][0]++;  //利用第一个位置存数的个数
                break;
            }
        }
    }

    int ans = -1;  //最终答案
    int tmp = 0;   //中间答案

    for (i = 0; i < k; i++) {
        for (j = 0; j < k; j++) {
            d = (2 * k - i - j) % k;
            //五种情况，注意如果没有那么多个数的话就不要更新，直接跳过，以免出错
            if (i == j && j == d && a[i][0] >= 3) {
                tmp = a[i][1] + a[i][2] + a[i][3];
            } else if (i != j && i != d && j != d && a[i][0] >= 1 &&
                       a[j][0] >= 1 && a[d][0] >= 1) {
                tmp = a[i][1] + a[j][1] + a[d][1];
            } else if (i == j && i != d && a[i][0] >= 2 && a[d][0] >= 1) {
                tmp = a[i][1] + a[i][2] + a[d][1];
            } else if (i == d && i != j && a[i][0] >= 2 && a[j][0] >= 1) {
                tmp = a[i][1] + a[i][2] + a[j][1];
            } else if (j == d && i != j && a[j][0] >= 2 && a[i][0] >= 1) {
                tmp = a[j][1] + a[j][2] + a[i][1];
            }
            ans = max(ans, tmp);
        }
    }
    printf("%dn", ans);
}

int main(void) {
    solve();
    return 0;
}