首页 > 代码库 > UVa1152 4 Values whose Sum is 0 (中途相遇法)
UVa1152 4 Values whose Sum is 0 (中途相遇法)
链接:http://vjudge.net/problem/36014
分析:先枚举a和b,把所有a+b记录下来放在一个有序数组中,然后枚举c和d,查一查-c-d有多少种方法写成a+b的形式(二分查找)。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 4000 + 5; 6 7 int a[maxn], b[maxn], c[maxn], d[maxn]; 8 int ab[maxn * maxn], cd[maxn * maxn]; 9 10 int main() {11 int T;12 scanf("%d", &T);13 while (T--) {14 int n;15 scanf("%d", &n);16 for (int i = 0; i < n; i++) scanf("%d%d%d%d", &a[i], &b[i], &c[i], &d[i]);17 for (int i = 0; i < n; i++)18 for (int j = 0; j < n; j++) ab[i * n + j] = a[i] + b[j];19 for (int i = 0; i < n; i++)20 for (int j = 0; j < n; j++) cd[i * n + j] = -(c[i] + d[j]);21 sort(cd, cd + n * n);22 long long ans = 0;23 for (int i = 0; i < n * n; i++)24 ans += upper_bound(cd, cd + n * n, ab[i]) - lower_bound(cd, cd + n * n, ab[i]);25 printf("%lld\n", ans);26 if(T) printf("\n");27 }28 return 0;29 }
UVa1152 4 Values whose Sum is 0 (中途相遇法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。