首页 > 代码库 > POJ - 2785 - 4 Values whose Sum is 0 - 二分折半查找
POJ - 2785 - 4 Values whose Sum is 0 - 二分折半查找
2017-08-01 21:29:14
writer:pprp
参考:http://blog.csdn.net/piaocoder/article/details/45584763
算法分析:直接暴力复杂度过高,所以要用二分的方法,分成两半复杂度就会大大降低;
题目意思:给定4个n(1<=n<=4000)元素的集合 A、B、C、D ,从4个集合中分别选取一个元素a, b,c,d。求满足 a+b+c+d=0的个数
代码如下:
//首先将前两列任意两项相加得到数组x,再将后两列任意两项相加取反得到数组y, //再将y排序,最后依次将x中的元素在y中进行 //二分查找,看有多少个相等的数加起来即为最终的结果。 #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int a[4010][4]; int x[16000001]; int y[16000001]; int ll, ans; //search x[i] from array y[i] void bit_search(int t) { int mid,l = 0,r = ll - 1; while(l < r) { mid = (l+r) >> 1; if(y[mid] < t) l = mid + 1; else r = mid; } while(y[l] == t && l < ll) //可能有找到不止一个 { ans++; l++; } } int main() { int n,i,j; while(cin >> n) { ans = 0,ll = 0; for(i = 0; i < n; i++) //record the data cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3]; for(i = 0; i < n; i++) //枚举左侧 { for(j = 0; j < n ; j++) { x[ll++] = a[i][0] + a[j][1]; } } ll = 0; for(i = 0; i < n ; i++) //枚举右侧 { for(j = 0; j < n ; j++) { y[ll++] = -(a[i][2] + a[j][3]); //这里取反 a + b + c + d = 0等价于a + b = -(c + d); } } sort(y,y+ll); //先排序 for(i = 0 ; i < ll ; i++) //再进行二分查找,如果找到那么ans++ bit_search(x[i]); cout << ans << endl; } return 0; }
POJ - 2785 - 4 Values whose Sum is 0 - 二分折半查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。