二分写法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
// 10 485
// 15 54 31 17 87 10 74 77 100 24
typedef long long LL;
const int N = 36;
int n, m, q[N];
int path[N];
bool st[N];
int ans = 0;
int add(int len)
{
int res = 0;
for (int i = 0; i < len; i ++)
{
res += path[i];
}
return res;
}
void dfs(int u, int k, int sum, vector<int>& way)
{
if (u == k)
{
way.push_back(sum);
// return;
}
else
{
// 选择当前枚举到的数
dfs(u + 1, k, (sum + q[u]) % m, way);
// 不选当前枚举到的数
dfs(u + 1, k, sum, way);
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++) cin >> q[i];
vector<int> A, B;
dfs(0, n / 2, 0, A);
dfs(n / 2, n, 0, B);
sort(A.begin(), A.end());
sort(B.begin(), B.end());
// 二分写法,对于每一个A中的元素,二分出B中与A当前元素相加小于m的最大值,计算对m取模的值,枚举完A中所有的元素,即可获得答案
for (int i = 0; i < A.size(); i ++)
{
int l = 0, r = B.size() - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (B[mid] + A[i] < m) l = mid;
else r = mid - 1;
}
res = max(res, (B[l] + A[i]) % m);
}
cout << res << endl;
return 0;
}
双指针写法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
// 10 485
// 15 54 31 17 87 10 74 77 100 24
typedef long long LL;
const int N = 36;
int n, m, q[N];
int path[N];
bool st[N];
int ans = 0;
int add(int len)
{
int res = 0;
for (int i = 0; i < len; i ++)
{
res += path[i];
}
return res;
}
void dfs(int u, int k, int sum, vector<int>& way)
{
if (u == k)
{
way.push_back(sum);
// return;
}
else
{
// 选择当前枚举到的数
dfs(u + 1, k, (sum + q[u]) % m, way);
// 不选当前枚举到的数
dfs(u + 1, k, sum, way);
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++) cin >> q[i];
vector<int> A, B;
dfs(0, n / 2, 0, A);
dfs(n / 2, n, 0, B);
sort(A.begin(), A.end());
sort(B.begin(), B.end());
// 计算[m, 2m - 2]区间,因为大于m并且值越大,那么对m取模也会越大
int res = (A.back() + B.back()) % m;
// 计算[0, m - 1]区间,只有A + B < m才计算对m的模,因为计算大于m的没有意义
// 并且我们计算的也是在[0, m - 1]区间里面的较大的值
for (int i = 0, j = B.size() - 1; i < A.size(); i ++)
{
while (j > 0 && A[i] + B[j] >= m) j --;
if (j >= 0) res = max(res, (A[i] + B[j]) % m);
}
cout << res << endl;
return 0;
}