AcWing 1698. 余数的最大值
宋标 Lv5
  2022-08-18 02:30:57 2022-08-18 02:30    

题目

给定一个包含 个正整数的序列，再给定一个正整数 。

请你求出该序列的子序列的各元素之和对 取模的最大值。

输入格式

第一行包含两个整数 和 。

第二行包含 个正整数。

输出格式

输出一个整数表示结果。

数据范围

,
,

输入样例：

3 5
2 7 8

输出样例：

4

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
#include <vector>
#define N 40

using namespace std;

int n, m;
int w[N];
vector<int> A, B;

void dfs(int u, int k, int sum, vector<int>& vec)
{
    if (u == k) 
    {
        vec.push_back(sum % m);
        return;
    }
    dfs(u + 1, k, sum + w[u], vec);
    dfs(u + 1, k, sum, vec);
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; ++ i) cin >> w[i];

    dfs(0, n / 2, 0, A);
    dfs(n / 2, n, 0, B);

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    // 当和大于m时, 取两个集合的最大值取余
    int res = (A.back() + B.back()) % m;

    // 当和小于m时，取两个集合最接近m的最大值    
    for (int i = 0, j = B.size() - 1; i < A.size() && ~j; ++ i)
    {
        while (~j && A[i] + B[j] >= m) -- j;
        if (~j) res = max(res, (A[i] + B[j]) % m);
    }

    cout << res << endl;

    return 0;
}
 评论