UVa 1152 - 4 Values Whose Sum Is 0(中途相遇)

给出四个数组a、b、c、d,每个取一个数字,求有多少种取法使得和值为0。

枚举a、b中的和,查找c、d中的和的相反数有没有与a、b的和相等的。O(n^2*logn)的算法,如书上所说的,使用multiset和count超时了,改用
数组之后Ac。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=4010;
int a[4][maxn],sum[maxn*maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,p=0,cnt=0;
scanf("%d",&n);
memset(sum,0,sizeof(sum));
for(int i=0;i<n;++i)
for(int j=0;j<4;++j)
scanf("%d",&a[j][i]);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
sum[p++]=a[0][i]+a[1][j];
sort(sum,sum+p);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
cnt+=upper_bound(sum,sum+p,-a[2][i]-a[3][j])-lower_bound(sum,sum+p,-a[2][i]-a[3][j]);
printf("%d\n",cnt);
if(t) printf("\n");
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包