（白书训练计划）UVa 1152 4 Values whose Sum is 0（中途相遇法。。）

本文主要是介绍（白书训练计划）UVa 1152 4 Values whose Sum is 0（中途相遇法。。），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：UVa 1152

先枚举A集合与B集合的和，存起来，然后再枚举C集合与D集合的和，看与存起来的值有多少个是互为相反数的。水题。找存起来的值时可以用二分找。

代码如下：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
int a[5000], b[5000], c[6000], d[6000], p[17000000];
int main()
{int t, n, m, ans, i, j, k;scanf("%d",&t);while(t--){scanf("%d",&n);m=0;for(i=0;i<n;i++){scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);}for(i=0;i<n;i++){for(j=0;j<n;j++){p[m++]=a[i]+b[j];}}sort(p,p+m);int low, high, mid;ans=0;for(i=0;i<n;i++){for(j=0;j<n;j++){int x=-c[i]-d[j];low=0, high=m-1;while(low<=high){mid=low+high>>1;if(p[mid]>x) high=mid-1;else if(p[mid]<x) low=mid+1;else{for(k=mid;k>=0;k--){if(p[k]==x){ans++;}elsebreak;}for(k=mid+1;k<m;k++){if(p[k]==x){ans++;}elsebreak;}break;}}}}printf("%d\n",ans);if(t)puts("");}return 0;
}

这篇关于（白书训练计划）UVa 1152 4 Values whose Sum is 0（中途相遇法。。）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---