首页 > 代码库 > 【A + B + C + D】 问题
【A + B + C + D】 问题
A + B + C + D
Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 130 Accepted Submission(s): 44
Problem Description
Little Robert asked his mother for two cents. "What did you do withthe money I gave you yesterday?""I gave it to a poor old woman," heanswered."You‘re a good boy," said the mother proudly. "Here aretwo cents more. But why are you so interested in the oldwoman?""She is the one who sells the candy."A joke, hereentered
Below n four tuple (A, B, C, D), respectively, from the A, B, C, Dselected a, b ,c ,d To calculate the number of combinations ofa+b+c+d = 0;
Below n four tuple (A, B, C, D), respectively, from the A, B, C, Dselected a, b ,c ,d To calculate the number of combinations ofa+b+c+d = 0;
Input
The first line of the input file contains the size of the lists n(1<= n <= 4000)
Then every line containing four integer values (with absolute valueas large as 2^28 )
Then every line containing four integer values (with absolute valueas large as 2^28 )
Output
For each input file, your program has to write the number whose sumis zero
Sample Input
6 -45 22 42
-16 -41 -27 56
30 -36 53 -37
77 -36 30 -75
-46 26 -38-10
62 -32 -54 -6 45
Sample Output
5
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int maxn=4010;int n;int s1[maxn*maxn];int s2[maxn*maxn];int a[maxn],b[maxn],c[maxn],d[maxn];int main(){// freopen("in.txt", "r", stdin); while(~scanf("%d", &n)) {for (int i=0;i<n;i++) scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); for (int i=0;i<n;i++) for (int j=0;j<n;j++) s1[i*n+j]=a[i]+b[j]; for (int i=0;i<n;i++) for (int j=0;j<n;j++) s2[i*n+j] = c[i]+d[j]; sort(s1,s1+n*n); sort(s2,s2+n*n); int r = n*n-1; int ans =0; for (int i=0;i<n*n;i++) { while(r>=0 && s1[i]+s2[r]>0) r--; if (r < 0)break; int tmp = r; while (tmp >= 0 && s1[i]+s2[tmp] == 0) ans++, tmp--; } printf("%d\n", ans); } return 0;}
【A + B + C + D】 问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。