UVa 1152 - 4 Values whose Sum is 0（中途相遇）

发表于 分类于 ， Disqus：

给出四个数组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博客，格式可能有所偏差。 **

相关文章