POJ-2785 4 Values whose Sum is 0（二分+双指针）

POJ-2785 4 Values whose Sum is 0

在学习二分法的时候，偶然看到一道非常不错的题目，可以对今后的思维有一定启发~

题目描述：

4 Values whose Sum is 0

Time Limit: 15000MS		Memory Limit: 228000K
Total Submissions: 38477		Accepted: 11718
Case Time Limit: 5000MS

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 228 ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Sample Output

5

Hint

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

Source

Southwestern Europe 2005

试题的中文翻译版本（知道你们懒得看英文O(∩_∩)O）：

题目背景

wq突然喜欢上了喜欢寻宝游戏~

题目描述

有一天他发现了4个宝箱，每个宝箱都有n个宝物，并且每个宝物都有一个魔法值，问你现在有多少种情况选出的4个宝物魔法值为0

输入格式

第1行：n 代表宝箱中宝物的个数

第2~n+1行：依次输入4个宝箱中宝物的魔法值，每行4个数

输出格式

输出不同组合的个数。

输入输出样例

输入 #1

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

输出 #1

5

说明/提示

对样例的解释：

分别有{-45, -27, 42, 30}, {26, 30, -10, -46}, {-32, 22, 56, -46},{-32, 30, -75, 77}, {-32, -54, 56, 30}这五种组合

数据规模：

前50%：1<=n<=20,-1000<=a,b,c,d<=1000

后50%：1<=n<=1000,-30000<=a,b,c,d<=30000

注意：数据已在原题基础上减弱，不要求用最难的方法解题，欢迎hack数据

分析：

题目很明确，告诉我们有4列数，要我们从每一列取出一个数字，使得四个数的和为0

思路1：4重for循环，检验4个数的和是否为0，时间复杂度$O(N^4)$O(N4)

思路2：3重for循环，枚举前3列的数字，求出所有数和的可能性，这里我们设为A，然后扫一遍第4列，找所有的-A，-A的个数即为ans，时间复杂度$O(N^3+N)$O(N3+N)

思路3：由于只有4列，所以分成两组 A，B，每组含n^2个元素，即该组两列元素枚举出所有的和。然后A从小到大，B从大到小，找出Ai=（-Bj） 的所有情况，统计一下，就是最后的解。具体方法：开两个变量i,j，i指向s1[0]，j指向s2[n*n-1]，来一遍双指针法，时间复杂度$O(N^2+(NlogN)^2+N)$O(N2+(NlogN)2+N)，最终时间复杂度$O(N^2logN)$O(N2logN)

Code：

/*poj-2785*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#define int long long
typedef long long ll;
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[4001][4001],s1[4000*4000],s2[4000*4000];
signed main(){
    js;
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            for(int j=0;j<4;j++){
                cin>>a[i][j];
            }
        }
        int l1=0,r1=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                s1[l1++]=a[i][0]+a[j][1];//处理前两列的和
                s2[r1++]=a[i][2]+a[j][3];//处理后两列的和
            }
        }
        sort(s1,s1+n*n);
        sort(s2,s2+n*n);
        int cnt=0;
        int l=0,r=n*n-1;//双指针，一个在前，一个在后
        for(int i=0;i<n*n;i++){
            while(r>=0&&s1[i]+s2[r]>0){//r指针逐渐往前扫，直到s1[i]+s2[r]<=0退出循环
                r--;
            }
            if(r<0) break;//r出界，break
            int num=r;//用num临时存储r
            while(s1[i]+s2[num]==0&&num>=0){
                cnt++;
                num--;
            }
        }
        cout<<cnt<<endl;
    }
    //成功AC
}

目前最可以接受的方法如上所述，时间复杂度基本优化到最低，要注意原题的数据规模达到了$2e28$2e28

希望对你能有所启发????~