首页 > 代码库 > POJ 2785 4 Values whose Sum is 0
POJ 2785 4 Values whose Sum is 0
传送门:http://poj.org/problem?id=2785
解题思路:
从这四个数列中选择的话总有n的4次方中情况,所以全部判断一遍不可行。不过将他们对半分成AB和CD再考虑的话就可以解决了。从两个数列中选择的话只有n的2次方中组合。所以可以枚举。从A,B中取出a,b后,为了使总和为0则需要从C,D中取出a+b=-(c+d);先将a和b数组的和存在一个数组ab里面,再将c和d相加的相反数-(c+d)在ab数组里面查找,用的是二分查找。
实现代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MAXN=4005; int a[MAXN][4]; int b[MAXN*MAXN]; void solve(int n){ memset(b,0,sizeof(b)); for(int i=0;i<n;i++) for(int j=0;j<n;j++) b[i*n+j]=a[i][0]+a[j][1]; sort(b,b+(n*n)); int ans=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ int tmp=-(a[i][2]+a[j][3]); ans+=upper_bound(b,b+(n*n),tmp)-lower_bound(b,b+(n*n),tmp); } printf("%d\n",ans); } int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++) for(int j=0;j<4;j++) scanf("%d",&a[i][j]); solve(n); }
POJ 2785 4 Values whose Sum is 0
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。