[蓝桥杯2018初赛]倍数问题

题目描述

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

输入

第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。
1 <= n <= 10^5, 1 <= K <= 10^3，给定的 n 个数均不超过 10^8。

输出

输出一行一个整数代表所求的和。

样例输入

4 3
1 2 3 4

样例输出

9

分析：首先看这个题，从n个数中选三个数，且三个数相加的和是k的倍数，且满足倍数中最大。

那么这一看就是背包空间3，选数满足特殊要求，的01背包吧。

现在分析怎么才能构成k的倍数, 假设我们 k=3，要选一个数4，要让它构成3的倍数，然后要选另一个数，

那么另一个数要让它余数为零，则要找余数为(0 – x%k + k)%k的数，则推出两个数相加要求余数不变，则满足（当前余数 - x%k + k）%k的数。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

const int N = 1010;

int n, m;
vector<int> a[N];
int f[4][N];//4代表当前选的数，N代表余数 

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        a[x % m].push_back(x);//将数按余数分组 
    }

    memset(f, -9999, sizeof f);
    f[0][0] = 0;

    for (int i = 0; i < m; i ++ )//枚举余数背包 
    {
        sort(a[i].rbegin(), a[i].rend());//从大到小排序 

        for (int u = 0; u < 3 && a[i].size() > u; u ++ )//每个分组最多选三个最大的 
        {
            int x = a[i][u];

            for (int j = 3; j >= 1; j -- )
                for (int k = 0; k < m; k ++ ){//枚举余数 

                    f[j][k] = max(f[j][k], f[j - 1][(k - x%m + m) % m] + x);
                    //f[j - 1][(k - x%m + m) % m] + x保证相加后的余数还为k 
                }
        }
    }

    printf("%d\n", f[3][0]);//输出我们要的余数为零的数 

    return 0;
}