首页 > 代码库 > POJ 2785 4 Values whose Sum is 0
POJ 2785 4 Values whose Sum is 0
题目链接：http://poj.org/problem?id=2785
思路：
朴素的枚举算法时间复杂度到了O(n^4),肯定会超时，这里我们用到了折半枚举的方法～ 原理就是先算前两个数组的各个元素进行枚举的和，排序后，然后再枚举后面两个数组各个元素的和，是这两块的和为0，而这部操作可以用到二分搜索的思想来优化。所以时间复杂度优化成了O(n^2*logn).
代码：
#include <iostream>#include <algorithm>using namespace std;int a[4001],b[4001],c[4001],d[4001];int cd[4001*4001];int main(){ int n; while(cin>>n) { for(int i=0;i<n;i++) { cin>>a[i]>>b[i]>>c[i]>>d[i]; } //枚举第一部分 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cd[n*i+j] = c[i]+d[j]; } } //排序 sort(cd,cd+n*n); long long res = 0; //枚举第二部分 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int ab = -(a[i]+b[j]); //二分思想查找值 res += upper_bound(cd,cd+n*n,ab) - lower_bound(cd,cd+n*n,ab); } } cout<<res<<endl; } return 0;}
POJ 2785 4 Values whose Sum is 0
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。