首页 > 代码库 > POJ 2785 4 Values whose Sum is 0 [二分]
POJ 2785 4 Values whose Sum is 0 [二分]
传送门
| 13773503 | njczy2010 | 2785 | Accepted | 25248K | 7079MS | G++ | 1423B | 2015-01-11 10:26:48 |
4 Values whose Sum is 0
| Time Limit: 15000MS | Memory Limit: 228000K | |
| Total Submissions: 16102 | Accepted: 4659 | |
| Case Time Limit: 5000MS | ||
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).
Source
Southwestern Europe 2005
sign，抱着脑袋想了好久怎么用hash做，就是没想着用二分，，，，，，
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<string>12 13 #define N 400214 #define M 1015 #define mod 100000000716 //#define p 1000000717 #define mod2 100000000018 #define ll long long19 #define LL long long20 #define eps 1e-921 #define inf 0x3fffffff22 #define maxi(a,b) (a)>(b)? (a) : (b)23 #define mini(a,b) (a)<(b)? (a) : (b)24 25 using namespace std;26 27 int x[N*N];28 int a[N],b[N],c[N],d[N];29 ll ans;30 int k;31 int n;32 33 void ini()34 {35 int i,j;36 ans=0;37 for(i=1;i<=n;i++){38 scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);39 }40 k=0;41 for(i=1;i<=n;i++){42 for(j=1;j<=n;j++){43 x[k]=a[i]+b[j];k++;44 }45 }46 sort(x,x+k);47 }48 49 void solve()50 {51 int i,j;52 int te;53 int t1,t2;54 for(i=1;i<=n;i++){55 for(j=1;j<=n;j++){56 te=-c[i]-d[j];57 t1=lower_bound(x,x+k,te)-x;58 t2=upper_bound(x,x+k,te)-x;59 ans+=(ll)(t2-t1);60 }61 }62 }63 64 void out()65 {66 printf("%I64d\n",ans);67 }68 69 int main()70 {71 //freopen("data.in","r",stdin);72 // freopen("data.out","w",stdout);73 //scanf("%d",&T);74 //for(int ccnt=1;ccnt<=T;ccnt++)75 //while(T--)76 while(scanf("%d",&n)!=EOF)77 {78 ini();79 solve();80 out();81 }82 83 return 0;84 }
POJ 2785 4 Values whose Sum is 0 [二分]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。