折半枚举（双向搜索） —— 4 Values whose Sum is 0 POJ - 2785 题解

﹏ヽ暗。殇╰゛Y 2022-09-03 00:23 3阅读 0赞

## 题目链接 ##

> https://vjudge.net/problem/POJ-2785

## 题目简述 ##

> 有ABCD四个数组，从每个数组中选取出一个元素，求和为0的所有组合总数。

## 题目解析 ##

每个都枚举肯定是不行的，复杂度O（n^4）.

可以考虑独立出一个来，然后求A+B+C的和，然后对D排序，二分搜索D的值,  
复杂度O（n^3 \* log(n)），不太够，再度优化

可以看成 a + b = - c - d  
先求C+D的和，看做一个新的数组cd，对cd排序  
然后枚举A+B，再二分搜索cd的值，  
时间复杂度O(n^2 \* log(n))  
但空间复杂度从O(n)到了O(n^2)，不过相对于时间的开销，空间的开销是值得的。

## AC代码 ##

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int n;
    const int max_n = 4000;
    int a[max_n];
    int b[max_n];
    int c[max_n];
    int d[max_n];
    int cd[max_n * max_n];
    
    void solve()
    {
        
        for (int i = 0; i < n; ++i)
        {
        
            for (int j = 0; j < n; ++j)
            {
        
                cd[i * n + j] = -c[i] - d[j];
            }
        }
        
        sort(cd, cd + n * n);
        
        long long res = 0;
        for (int i = 0; i < n; ++i)
        {
        
            for (int j = 0; j < n; ++j)
            {
        
                int ab = a[i] + b[j];
                res += upper_bound(cd, cd + n * n, ab) 
                        - lower_bound(cd, cd + n * n, ab);
            }
        }
        
        cout << res << endl;
    }
    
    int main()
    {
        
        cin.tie(0);
        cout.tie(0);
        ios::sync_with_stdio(false);
        
        cin >> n;
        for (int i = 0 ; i < n; ++i)
        {
        
            cin >> a[i] >> b[i] >> c[i] >> d[i];
        }
        
        solve();
        return 0;
    }