版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434642
挑战程序竞赛系列（23）：3.2折半枚举
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
- POJ 2785: 4 Values whose Sum is 0
- POJ 3977: Subsets
- POJ 2549: Sumsets
POJ 2785: 4 Values whose Sum is 0
基本想法：
全部枚举，判断sum == 0，时间复杂度为O(n4)O(n^4)，优化，折半枚举。
确定sum意味着给定两个组合，另外一半也将确定，所以可以给出任意两个元素的所有组合，进行折半搜索。sum = a b，a确定b跟着确定，这是折半的核心思想。这样b的搜索可以采用二分。
总的来说，sum并不关系每个独立的个体具体是什么值，它只关心总和是否等于算，所以sum = a b c d和sum = (a b) (c d)，对于sum来说没有区别。既然无区别，干嘛要用独立性如此高的算法O(n4)O(n^4)来实现呢？
当(a b)看成整体后，它的搜索成本自然就下去了。
代码如下：
代码语言：javascript复制 void solve() {
int n = ni();
int[] A = new int[n];
int[] B = new int[n];
int[] C = new int[n];
int[] D = new int[n];
for (int i = 0; i < n; i){
A[i] = ni();
B[i] = ni();
C[i] = ni();
D[i] = ni();
}
int[] arra = new int[n * n];
for (int i = 0, k = 0; i < n; i){
for (int j = 0; j < n; j){
arra[k ] = C[i] D[j];
}
}
Arrays.sort(arra);
long cnt = 0;
for (int i = 0; i < n; i){
for (int j = 0; j < n; j){
int key = -(A[i] B[j]);
int lo = lowBound(arra, key);
int hi = upBound(arra, key);
if (lo == -1 || hi == -1) continue;
cnt = (hi - lo 1);
}
}
out.println(cnt);
}
private int lowBound(int[] arra, int key){
int lf = 0, rt = arra.length - 1;
while (lf < rt){
int mid = lf (rt - lf) / 2;
if (arra[mid] < key) lf = mid 1;
else rt = mid;
}
if (arra[rt] == key) return rt;
return -1;
}
private int upBound(int[] arra, int key){
int lf = 0, rt = arra.length - 1;
while (lf < rt){
int mid = lf (rt - lf 1) / 2;
if (arra[mid] > key) rt = mid - 1;
else lf = mid;
}
if (arra[lf] == key) return lf;
return -1;
}POJ 3977: Subsets
全部枚举需要O(2n)O(2^n)次方，OJ不让过，所以可以采用折半的思路，此题和上题相似，无非由于子集的个数不确定，所以有sum = a b c …这种情况，且sum不是固定的值，而是尽可能接近0，天啊噜，改了20多次，依旧WA。
思路：
对数据进行划分，分成n/2和n - n/2的两个子集，分别对子集中的所有可能组合枚举，分别得到两个sum1和sum2，令sum1 sum2尽可能的接近0，所以只要针对某个sum集合进行排序，二分。
- 用二分法逼近答案，因为可能会有多解的情况
- 所以需要进行两次，第一次寻找最接近0的负值，第二次寻找最接近0的正值。
- 然后扫描这两者之间的所有元素，找出sum最小，且count最小的组合
自己代码如下：
代码语言：javascript复制 public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
int n = new Integer(br.readLine());
if (n == 0) break;
long[] arra = new long[n];
String input[] = br.readLine().split("\s");
for (int i = 0; i < n; i ) {
arra[i] = new Long(input[i]);
}
long[] LL = new long[n];
long[] RR = new long[n];
int LN = 0, RN = 0;
for (int i = 0; i < n; i = 2) {
LL[LN ] = arra[i];
if (i 1 < n)
RR[RN ] = arra[i 1];
}
if (RN == 0) {
System.out.println(LL[0] " " 1);
continue;
}
Sum[] sums = new Sum[1 << RN];
for (int i = 0; i < 1 << RN; i) {
long sum = 0;
int cnt = 0;
for (int j = 0; j < RN; j) {
if ((i & (1 << j)) != 0) {
sum = RR[j];
cnt ;
}
}
sums[i] = new Sum(sum, cnt);
}
Arrays.sort(sums);
long ans = 1000000000000001l;
int ansc = 36;
for (int i = 0; i < 1 << LN; i) {
long key = 0;
int cnt = 0;
for (int j = 0; j < LN; j) {
if ((i & (1 << j)) != 0) {
key = LL[j];
cnt ;
}
}
int l = 0;
int r = sums.length;
while (r - l > 1) {
int m = (l r) / 2;
if (sums[m].sum key >= 0) {
r = m;
} else {
l = m;
}
}
int L = l;
l = -1;
r = sums.length - 1;
while (r - l > 1) {
int m = (l r) / 2;
if (sums[m].sum key > 0) {
r = m;
} else {
l = m;
}
}
int R = r;
for(int k = L; k <= R; k){
long tempsum = Math.abs(sums[k].sum key);
int tempcount = sums[k].cnt cnt;
if (tempcount == 0) continue;
if(tempsum < ans){
ans = tempsum;
ansc = tempcount;
}
else if(tempsum == ans & tempcount < ansc){
ansc = tempcount;
}
}
}
System.out.println(ans " " ansc);
}
}WA到心碎，正确代码可以参考http://poj.org/showmessage?message_id=346495
POJ 2549: Sumsets
思路：
a b = d - c，所以把等式两边表示出来用个二分就解决了，一开始二分（a b），但枚举（d-c）需要的次数较大，所以二分（d-c），枚举（a b），此时只需要n⋅(n−1)/2n cdot (n - 1) / 2次的二分查询，勉强过了。前者TLE了。
代码如下：
代码语言：javascript复制 void solve() {
while (true){
int n = ni();
if (n == 0) break;
long[] arra = new long[n];
Map<Long, Integer> map = new HashMap<Long, Integer>();
for (int i = 0; i < n; i){
arra[i] = nl();
if (!map.containsKey(arra[i])){
map.put(arra[i], 0);
}
map.put(arra[i], map.get(arra[i]) 1);
}
TwoSum[] sums = new TwoSum[n * n];
for (int i = 0; i < sums.length; i){
sums[i] = new TwoSum(Long.MAX_VALUE, -1, -1);
}
int N = 0;
for (int i = 0; i < n; i){
if (map.get(arra[i]) != 1) continue;
for (int j = 0; j < n; j){
if (i == j) continue;
sums[N ] = new TwoSum(arra[i] - arra[j], i, j);
}
}
Arrays.sort(sums);
long max = Long.MIN_VALUE;
for (int i = 0; i < n; i){
for (int j = i 1; j < n; j){
long key = arra[i] arra[j];
int lo = loBound(sums, N, key);
int hi = upBound(sums, N, key);
if (lo == -1 || hi == -1) continue;
for (int l = lo; l <= hi; l){
TwoSum sum = sums[l];
if (sum.i == i || sum.j == i || sum.i ==j || sum.j == j) continue;
max = Math.max(arra[sum.i], max);
}
}
}
if (max == Long.MIN_VALUE) out.println("no solution");
else out.println(max);
}
}
public int upBound(TwoSum[] sums, int len, long key){
int lf = 0, rt = len - 1;
while (lf < rt){
int mid = lf (rt - lf 1) / 2;
if (sums[mid].sum > key) rt = mid - 1;
else lf = mid;
}
if (sums[lf].sum == key) return lf;
return -1;
}
public int loBound(TwoSum[] sums, int len, long key){
int lf = 0, rt = len - 1;
while (lf < rt){
int mid = lf (rt - lf) / 2;
if (sums[mid].sum < key) lf = mid 1;
else rt = mid;
}
if (sums[rt].sum == key) return rt;
return -1;
}
class TwoSum implements Comparable<TwoSum>{
long sum;
int i;
int j;
public TwoSum(long sum, int i, int j) {
this.sum = sum;
this.i = i;
this.j = j;
}
@Override
public String toString() {
return "" sum;
}
@Override
public int compareTo(TwoSum o) {
return this.sum < o.sum ? -1 : 1;
}
}
