4 Values whose Sum is 0 [POJ2785] [折半搜索]

发布时间：2020-12-14 03:21:41 所属栏目：大数据来源：网络整理

导读：题意给你长度为n四个数列，每个数列选一个数使总和为4，有多少种选法（不同选法仅当起码有一个元素的下标不同）输入第一行，n 下面n行，每行四个数，代表ai,bi,ci,di 输出选法数量样例输入 6-45 22 42 -16-41 -27 56 30-36 53 -37 77-36 30 -75 -4626 -

题意

给你长度为n四个数列，每个数列选一个数使总和为4，有多少种选法（不同选法仅当起码有一个元素的下标不同）

输入

第一行，n

下面n行，每行四个数，代表ai,bi,ci,di

输出

选法数量

样例输入

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

样例输出

分析

1、傻逼算法：四重枚举 O(n⁴)

2、优化一点的傻逼算法：三重枚举+一重二分O(n³logn)

3、比较优化算法：枚举c和d组成的数生成e，e排序，再枚举a，b，与e配对O(n²logn)

代码

 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<cmath>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<iostream>
 9 #include<algorithm>
10 #define RG register ll
11 #define rep(i,a,b)    for(RG i=a;i<=b;++i)
12 #define per(i,b)    for(RG i=a;i>=b;--i)
13 #define ll long long
14 #define inf (1<<29)
15 #define maxn 4005
16 using namespace std;
17 ll n,cnt,ans;
18 ll a[maxn],b[maxn],c[maxn],d[maxn],e[maxn*maxn];
19 inline ll read()
20 {
21     ll x=0,f=1;char c=getchar();
22     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
23     while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
24     return x*f;
25 }
26 
27 int main()
28 {
29     n=read();
30     rep(i,1,n)    a[i]=read(),b[i]=read(),c[i]=read(),d[i]=read();
31     rep(i,n)rep(j,n)    e[++cnt]=c[i]+d[j];
32     sort(e+1,e+1+cnt);
33     rep(i,1,n)
34         rep(j,n)
35         {
36             ll fd=-a[i]-b[j];
37             ans+=upper_bound(e+1,e+1+cnt,fd)-lower_bound(e+1,e+1+cnt,fd);
38         }
39     cout<<ans;
40     return 0;
41 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!