二分贪心练习题D-4

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  ²⁸ ) 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 题意： 就是输入几组数据，每组四个整数，找出每列选一个数，最后四个数加起来位0。求有多少种组珐。 分析： 如果用常规的的递归做法做的话一定超时，刚学了二分，总算强套上，用双循环算出前两列相加，后两列，可以得出的所有数，用二分找正好两边相加为零出现过多少次，累加。 细节： 见代码注释 #include <iostream> #include <algorithm> #include<stdio.h> #include<vector> #include<string.h> #include<string> using namespace std; int a[4005],b[4005],c[4005],d[4005],sum[16040025],o=0; int main() { int n,k=0,s,l,r,mid,q; cin>>n; for(int i=0; i<n; i++) { cin>>a[i]>>b[i]>>c[i]>>d[i]; } for(int i=0;i<n; i++) { for(int j=0;j<n; j++) { sum[k]=a[i]+b[j]; k++; } } sort(sum,sum+k); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { q=-c[i]-d[j]; l=0,r=k-1; while(l<=r) { mid=(l+r)/2; if(sum[mid]>q) r=mid-1; else if(sum[mid]<q) l=mid+1; else//正好找到 { for(s=mid;s>=0;s--)//有可能存在多个组合都加得了此数，向前找 { if(sum[s]==q) o++; else break; } for(s=mid+1; s<k; s++)//向后找 { if(sum[s]==q) o++; else break; } break; } } } } cout<<o; }