SP1296 SUMFOUR - 4 values whose sum is 0

解题思路

　　四个数组一起做有点炸。先把他们合并成两个数组，然后让一个数组有序，枚举另一个数组的元素，二分即可。时间复杂度\(O(n^2logn^2)\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int MAXN = 4005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int A[MAXN*MAXN],B[MAXN*MAXN],n,a[MAXN],b[MAXN],c[MAXN],d[MAXN];

int num[MAXN*MAXN],cnt,cnt2,cpy[MAXN*MAXN];

long long ans;

int main(){

	n=rd();int x,y,w,z;

	for(int i=1;i<=n;i++)

		a[i]=rd(),b[i]=rd(),c[i]=rd(),d[i]=rd();

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++) A[++cnt]=a[i]+b[j],B[cnt]=c[i]+d[j];

	sort(A+1,A+1+cnt);A[0]=(1<<28)+1;

	for(register int i=1;i<=cnt;i++){

		if(A[i]==A[i-1]) num[cnt2]++;

		else cpy[++cnt2]=A[i],num[cnt2]=1;

	}

//	for(int i=1;i<=cnt2;i++) cout<<cpy[i]<<" ";

//	A[++cnt2]=1;A[++cnt2]=2;A[++cnt2]=8;B[++cnt]=1;B[++cnt]=-2;B[++cnt]=-8;

	for(register int i=1;i<=cnt;i++) {

		x=lower_bound(cpy+1,cpy+1+cnt2,-B[i])-cpy;

//		cout<<x<<endl;

		if(cpy[x]==-B[i]) ans+=num[x];

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

SP1296 SUMFOUR - 4 values whose sum is 0

解题思路

代码

最新文章

热门文章