基础算法——折半枚举

折半枚举的题目一般的情景是如果所有情况均遍历会超时，如果只是选择一半的数据进行暴力枚举，则在时限内，一般会和哈希以及二分进行结合，利用哈希和二分来加速查找过程。

四数之和

• POJ-2785 4 Values whose Sum is 0（折半枚举）

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2 28 ) that belong respectively to A, B, C and D .

四个数组，从每个数组里选出一个数求和，问总和是0的组合有多少个。如果直接暴力枚举，每个组内4000个数据，$4000^4$肯定超时，如果选择将前两个数组的元素进行枚举，时间复杂度是$4000^2$可以接受，然后再枚举后半部分。第一部分枚举出来的结果进行排序，然后利用二分查找的lower_bound和upper_bound来找出可行范围，直接累加即可。

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> seq1(4005), seq2(4005), seq3(4005), seq4(4005);
vector<int> d(4005 * 4005);
int n;

int solve()
{
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i * n + j] = seq3[i] + seq4[j];
        }
    }

    sort(d.begin(), d.begin() + n * n);

    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int target = -(seq1[i] + seq2[j]);
            cnt += upper_bound(d.begin(), d.begin() + n * n, target) 
                - lower_bound(d.begin(), d.begin() + n * n, target);
        }
    }

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq1[i] >> seq2[i] >> seq3[i] >> seq4[i];
    }

    cout << solve() << endl;

    return 0;
}

典型题目

• POJ-2785 4 Values whose Sum is 0（折半枚举）
• HDU 1496
• POJ 2549
• POJ 3977