简单的二分.. 不过写挫了... 4000*4000我算成了16W... 丢死人了...交题果断RE,还百思不得其解....
后来改掉之后果断TLE了，自认算法没错，难道是函数调用的关系？
对比了一下AC程序发现在二分查找的过程中有一个break条件没加...
改掉之后ac了。另外发现sort的cmp调用十分的占时间。按照默认的升序sort吧，这样省时间。
以上为题解.
#include<iostream> #include<algorithm> #include<cstdio> #include<string.h> using namespace std;int sum1[16666666],sum2[16666666]; int num[4][4444]; int len;bool cmp( int a,int b ){ return a<b; }int BinarySeach( int k ) {int r=len-1,l=0,m;bool found=false;while( l<=r ){m=(l+r)/2;if( sum2[m]==k ){found=true;break;}else{if( sum2[m]>=k )r=m-1;elsel=m+1;}}if( !found )return 0;int cnt=1;l=m-1;r=m+1;for( int i=l;i>=0;i-- )if( sum2[i]==k ) cnt++;else break;for( int i=r;i<len;i++ )if( sum2[i]==k ) cnt++;else break;return cnt; }int main() {int N;while( scanf("%d",&N)!=EOF ){//memset( sum1,0,sizeof(sum1) );//memset( sum2,0,sizeof(sum2) );for( int i=0;i<N;i++ )scanf( "%d%d%d%d",&num[0][i],&num[1][i],&num[2][i],&num[3][i] );//二维数组比4个数组快 100ms len=0;for( int i=0;i<N;i++ )for( int j=0;j<N;j++ ){sum1[len]=num[0][i]+num[1][j];sum2[len++]=-num[2][i]-num[3][j];}//sort( sum1,sum1+len,cmp );//sort( sum2,sum2+len,cmp );//多加cmp, 时间+2400mssort( sum1,sum1+len );sort( sum2,sum2+len );int cnt=BinarySeach( sum1[0] );int rec=cnt;for( int i=1;i<len;i++ ){if( sum1[i]!=sum1[i-1] )//+判断 time -500ms rec=BinarySeach( sum1[i] );cnt+=rec;}printf( "%d\n",cnt );}return 0; }