题目链接：http://poj.org/problem?id=2785
题目大意： 给出四个长度为n的列表(从上到下)
从每个列表分别取出一个数据，使得相加的结果为0
问最多存在多少种情况?
解题思路： n的范围(1<=n<=4000)，如果直接搜索 O(n^4) 那么肯定TLE.(计算机每秒钟的运行速度大概是10^8)
可以转化为O(2*n^2)：
把1组和2组列表分别相加存到a[ ]数组中，3组和4组列表分别相加存到b[ ]数组中
只需要使得两个数组中元素a[i]=-b[j]，那么这样的组合相加的结果就为0！
如果用朴素搜索会超时，所以存到数组之后，先排序，然后用二分法查找；
有一组数据很容易错，可以参考一下：
PS：qsort居然会TLE，换成了sort就AC了，离线测试发现这道题用sort比qsort的效率高一倍！真奇怪
这道题还可以用Hash函数(散列函数)，稍后再写吧！
易错数据：
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
256
代码：
#include <stdio.h>
#include <stdlib.h>
#include<algorithm>
using namespace std;
#define MAX_2 4001
#define MAX 16100000
int num[MAX_2][4],left[MAX],right[MAX];
int ErFen(int a[],int n,int x) //二分查找，在数组right[]中查找x的位置，并且反馈x出现的次数
{
int pd=0,ant,lefts,rights,middle;
lefts=0;
rights=n-1;
while(lefts<=rights)
{
middle=(lefts+rights)>>1;
if(a[middle]==x)
{
pd=1;
break;
}
else if(x>a[middle]) lefts=middle+1;
else rights=middle-1;
}
if(pd)
{
for(ant=0;lefts<n;lefts++) //***这里是易错点，函数需要返回的是x出现的次数!
{
if(a[lefts]==x) ant++;
else if(ant!=0&&a[lefts]!=x) break;
}
return ant;
}
return -1;
}
int main()
{
int n,m,i,j,k,temp;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
for(j=0;j<4;j++)
{
scanf("%d",&num[i][j]);
}
}
for(i=0,k=0;i<n;i++)
{
for(j=0;j<n;j++)
{
left[k]=num[i][0]+num[j][1]; //1,2组列表相加
right[k++]=num[i][2]+num[j][3]; //3,4组列表相加
}
}
sort(left,left+k); //qsort排序会TLE
sort(right,right+k);
for(i=0,m=0;i<k;i++)
{
temp=ErFen(right,k,-left[i]); //*** right[j]=-left[i]则满足相加为0
if(temp!=-1)
m+=temp;;
}
printf("%d\n",m);
}
return 0;
}
注：原创文章，转载请注明出处