首页 > 代码库 > POJ2785-4 Values whose Sum is 0
POJ2785-4 Values whose Sum is 0
传送门：http://poj.org/problem?id=2785
Description
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
6-45 22 42 -16-41 -27 56 30-36 53 -37 77-36 30 -75 -4626 -38 -10 62-32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
给你一个数字n，然后有n组每组4个数，求每一列取出一个数，使最终四个数的和为0，求有多少种组合方式
解题思路：先求出来前两列和后两列的和，然后二分就可以了，对于这道题来说结果没有去重
1 #include<vector> 2 #include<set> 3 #include<stdio.h> 4 #include<algorithm> 5 using namespace std; 6 7 vector <int > a; 8 vector <int > b; 9 vector <int > c;10 vector <int > d;11 vector <int > sum1;12 vector <int > sum2;13 int main()14 {15 int n, i, j, a1, b1, c1, d1, sum;16 while(scanf("%d", &n)!=EOF) {17 sum = 0;18 for(i = 0; i < n; i++)19 {20 scanf("%d%d%d%d", &a1, &b1, &c1, &d1);21 a.push_back(a1);22 b.push_back(b1);23 c.push_back(c1);24 d.push_back(d1);25 }26 for(i = 0; i < n; i++) {27 for(j = 0; j < n; j++) {28 sum1.push_back(a[i] + b[j]);29 sum2.push_back(c[i] + d[j]);30 }31 }32 33 /* for(i = 0; i < sum1.size(); i++) {34 for(j = 0; j < sum2.size(); j++) {35 if(sum1[i]+sum2[j] == 0) {36 sum++;37 }38 }39 }*/40 n = sum2.size();41 sort(sum2.begin(),sum2.end());42 43 for(i = 0; i < n; i++) {44 int l = 0, r = n-1, mid;45 while(l <= r) {46 mid = (l + r) / 2;47 if(sum1[i] + sum2[mid] == 0) {48 sum++;49 for(j = mid + 1; j < n; j++) {50 if(sum1[i] + sum2[j] != 0) 51 break;52 else 53 sum++;54 }55 for(j = mid - 1; j >= 0; j--) {56 if(sum1[i] + sum2[j] != 0) 57 break;58 else 59 sum++;60 }61 break;62 }63 if(sum1[i] + sum2[mid] < 0) 64 l = mid + 1;65 else 66 r = mid - 1;67 }68 }69 printf("%d\n", sum);70 }71 return 0;72 }
POJ2785-4 Values whose Sum is 0
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。