Hust oj 1293 取数(Map)_综合

取数

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 382(84 users)

Total Accepted: 91(61 users)

Rating:

Special Judge: No

Description

有n个整数，给定一个数x，从n个数中取两个数，使得和刚好为x，问有多少种取法。

Input

有多组测试数据。

对于每组测试数据，有两行，第一行有两个数n, x，第二行有n个数, a1, a2, a3 ... an。

0 < n <= 100000, 0 <= x <= 1000000000, -1000000000 <= ai <= 1000000000。

Output

对于每组测试数据，输出一行，包含一个整数，有多少种取法。

Sample Input

2 5
1 4
3 10
5 5 5

Sample Output

因为只求两个数的和，那么我们可以用和与其中一个数的差来表示另一个数，用map存一下每个数的出现次数就可以了，但要注意

处理两个数相等时候的情况，而且最后结果要除2，因为总共找了两遍

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;const int Maxn = 100005;
typedef long long LL;
LL a[Maxn];
LL n,x;int main()
{while(~scanf("%lld %lld",&n,&x)){map<int ,LL>m;for(int i=0;i<n;i++){scanf("%lld",&a[i]);m[a[i]]++;}LL sum = 0;for(int i=0;i<n;i++){sum += m[x-a[i]];if(x-a[i] == a[i]){sum--;}}printf("%lld\n",sum/2);}return 0;
}