hihocoder [Offer收割]编程练习赛14小Hi和小Ho的礼物

题目1 : 小Hi和小Ho的礼物

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

某人有N袋金币，其中第i袋内金币的数量是Ai。现在他决定选出2袋金币送给小Hi，再选2袋金币送给小Ho，同时使得小Hi和小Ho得到的金币总数相等。他想知道一共有多少种不同的选择方法。

具体来说，有多少种下标四元组(i, j, p, q)满足i, j, p, q两两不同，并且i < j, p < q, Ai + Aj = Ap + Aq。

例如对于数组A=[1, 1, 2, 2, 2]，一共有12种选法：

i j p q

1 3 2 4

1 3 2 5

1 4 2 3

1 4 2 5

1 5 2 3

1 5 2 4

2 3 1 4

2 3 1 5

2 4 1 3

2 4 1 5

2 5 1 3

2 5 1 4

输入

第一行包含一个整数N。

第二行包含N个整数，A1, A2, A3 ... AN。

对于70%的数据，1 <= N <= 100

对于100%的数据，1 <= N <= 1000, 1 <= Ai <= 1000000

输出

不同选择的数目。

样例输入

5

1 1 2 2 2

样例输出

12

//按两数和统计一下 注意去掉i == p or j == q的情况

#include<map>

#include<cstdio>

#include<iostream>

using namespace std;

int n,a[(int)1e3+],cnt[(int)1e6+];

map<int,int>sum;long long ans;

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++) scanf("%d",a+i),cnt[a[i]]++;

    for(int i=;i<=n;i++) for(int j=i+;j<=n;j++) sum[a[i]+a[j]]++;

    for(int i=;i<=n;i++) for(int j=i+;j<=n;j++){

        ans+=sum[a[i]+a[j]];

        if(a[i]!=a[j])

            ans-=cnt[a[i]]+cnt[a[j]]-;

        else

            ans-=*(cnt[a[i]]-)-;

    }

    cout<<ans;

    return ;

}