CF888E - 最大余数[适合难度：普及+，提高-]，知识点：折半枚举，二分查找

本文主要是介绍CF888E - 最大余数[适合难度：普及+，提高-]，知识点：折半枚举，二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CF888E - 最大余数[适合难度：普及+，提高-]，知识点：折半枚举，二分查找

子集就是某一个组合

暴力枚举所有组合的复杂度为 $2^{35}$ ，不可接受

所以用上了折半枚举。。。。。。

折半枚举 + 二分查找，时间复杂度不超过 $2^{18}$ 。

折半枚举：

吧所有的数字拆成两半，暴力前一半数的所有组合，最多为 $2^{18}$ ，

保存到数组里进行排序。（预处理）

暴力枚举另外一半的所有组合。对于某一个组合的数，到数组里面去配对，去二分查找一个数，跟X加起来 $M O D M$ 最大，最后更新答案。

最终问题就变成了在一个有序的数组中查找某一个数，用二分解决。

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;vector <int> b;
vector <int> a;int tot;int find(int x)
{int best = -1;int l = 0, r = tot - 1;if(b[r] <= x){return b[r];}while(l <= r){int mid = (l + r) / 2;if(b[mid] <= x){best = b[mid];l = mid + 1;}else{r = mid - 1;}}return best;
}int main()
{int n, mod;scanf("%d%d", &n, &mod);int m = n / 2;for(int i = 0; i < n; i ++){int x;scanf("%d", &x);a.push_back(x % mod);}for(int i = 0; i < (1 << m); i ++){int tmp = 0;for(int j = 0; j < m; j ++){if(i & (1 << j)){tmp += a[j];tmp %= mod;}}b.push_back(tmp);}tot = b.size();sort(b.begin(), b.end());m = n - (n / 2);int mx = 0;for(int i = 0; i < (1 << m); i ++){int tmp = 0;for(int j = 0; j < m; j ++){if(i & (1 << j)){int jj = j + n / 2;tmp = (tmp + a[jj]) % mod;}}int x = find(mod - tmp - 1);mx = max(mx, (x + tmp) % mod);if(mx == mod - 1){break;}}printf("%d\n", mx);return 0;
}