第五题:T5最大的余数
标签:折半查找
题意:给定
n
n
n个数字
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a1,a2,…,an,在给定一个整数
m
m
m,请从给定的数字中挑选任意多个数字,使得它们的和模
m
m
m的余数尽量大,输出这个最大的余数。
(
1
≤
n
≤
40
,
1
≤
a
i
≤
1
0
9
,
1
≤
m
≤
1
0
9
)
(1≤n≤40,1≤a_i≤10^9,1≤m≤10^9)
(1≤n≤40,1≤ai≤109,1≤m≤109)
题解:一看到
n
≤
40
n≤40
n≤40,下意识就是折半查找,因为暴力搜索
2
40
≈
1
0
12
2^{40}≈10^{12}
240≈1012,肯定会超时。把问题折半一下,分别预处理出各自一半的数的组成情况,时间复杂度是
2
∗
2
20
≈
2
∗
1
0
6
2*2^{20}≈2*10^6
2∗220≈2∗106。
比如样例:
1
10
100
1000
10000
1 \ \ 10 \ \ 100 \ \ 1000 \ \ 10000
1 10 100 1000 10000
前两个的所有情况之和为
0
1
10
11
0 \ \ 1 \ \ 10 \ \ 11
0 1 10 11
后三个的所有情况之和为
0
100
1000
10000
1100
10100
11000
11100
0 \ \ 100 \ \ 1000 \ \ 10000 \ \ 1100 \ \ 10100 \ \ 11000 \ \ 11100
0 100 1000 10000 1100 10100 11000 11100
前半部分搜索出来的所有情况的值存到
b
b
b数组中,后半部分搜索出来的所以情况存到
c
c
c数组中。
要找出前半部分
+
+
+后半部分对
m
m
m进行取模余数尽可能大的。那我们可以枚举前半部分的所有情况,然后二分查找(
l
o
w
e
r
_
b
o
u
n
d
lower\_bound
lower_bound)一下后半部分中
m
−
b
[
i
]
m-b[i]
m−b[i]的值,找到的是第一个大于等于
m
−
b
[
i
]
m-b[i]
m−b[i]的,所以往前减一位即可。
代码:
#include <bits/stdc++.h>
using namespace std;
int n, m, a[50], ans = 0;
vector<int> b, c;
void dfs1(int p, int sum) {
if (p == n / 2 + 1) {
b.push_back(sum);
return ;
}
dfs1(p + 1, (sum + a[p]) % m);
dfs1(p + 1, sum % m);
}
void dfs2(int p, int sum) {
if (p == n + 1) {
c.push_back(sum);
return ;
}
dfs2(p + 1, (sum + a[p]) % m);
dfs2(p + 1, sum % m);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] %= m;
}
dfs1(1, 0);
dfs2(n / 2 + 1, 0);
sort(c.begin(), c.end());
for (int i = 0; i < b.size(); i++) {
int p = lower_bound(c.begin(), c.end(), m - b[i]) - c.begin();
p--;
ans = max(ans, (b[i] + c[p]) % m);
}
cout << ans << endl;
return 0;
}