4 Values whose Sum is 0
这个题目同上道二分的题目一样，只是把数字分成两堆，在排序用二分的思想，但是必须明白，不是在找到一个的条件的情况下跳出，可能只有重复的。这里是重点。继续我的二分之路，我的时间复杂度很高，效率不怎么好。看了下别人的代码，好像都是用hash，下一站就是hash了。
Case Time Limit: 5000MS#include<iostream>#include<cmath>#include<vector>#include<algorithm>#define maxn 4004using namespace std;int map1[maxn*maxn];int map2[maxn*maxn];int a[maxn],b[maxn],c[maxn],d[maxn];int main(){ int n,i,j,k,sum,p; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); } for(i=0;i<n;i++) for(j=0;j<n;j++) map1[i*n+j]=a[i]+b[j]; for(i=0;i<n;i++) for(j=0;j<n;j++) map2[i*n+j]=c[i]+d[j]; sort(map1,map1+n*n); sort(map2,map2+n*n); sum=0; p=n*n-1; for(i=0;i<n*n;i++) { while(p>=0&&map1[i]+map2[p]>0) p--; if(p<0) break; int temp=p; while(temp>=0&&map1[i]+map2[temp]==0) { sum++; temp--; } } printf("%d\n",sum); //system("pause"); return 0;}
