A-B 数对
题目描述
出题是一件痛苦的事情!
相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!
好吧,题目是这样的:给出一串数以及一个数字 C,要求计算出所有A−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。
输入格式
输入共两行。
第一行,两个整数 N,C。
第二行,N 个整数,作为要求处理的那串数。
输出格式
一行,表示该串数中包含的满足 A−B=C 的数对的个数。
输入输出样例
输入 #1
4 1
1 1 2 3
输出 #1
3
说明/提示
对于 75% 的数据,1≤N≤2000。
对于 100% 的数据1≤N≤2×105。
保证所有输入数据都在 32 位带符号整数范围内。
2017/4/29 新添数据两组
题目分析+解题思路
O(n2)思路
就是将A−B=C变成A=B+C,朴素的算法是一个二重循环,当然我们知道这肯定会超时的。
O(nlogn)思路
利用二分,一遍循环枚举找BBB,中间二分找C,时间复杂度O(nlogn),可以通过本题
也可以利用stlstlstl中自带的红黑树map达到AC的效果
O(n)思路
优化一点的算法呢则是用桶去保存每个数,这样我们就只需要枚举B,然后判断一下C存不存在就行了,这样的时间复杂度是O(n),当然此算法空间复杂度很高会MLE
正题
好吧,前面讲了这么多都是为了告诉你各算法的优缺点,自然在目前来看,HASHHASHHASH解法是最优秀的(除了打表),那么具体怎样实现呢?
实现
前面讲O(n)算法的时候,讲过用桶去做,这样的代价是用空间换时间,需要的空间代价是极高的,而HASH就是避免了这一点。
其实我们可以发现,桶数组中是有很多桶是没有用到的,也就是浪费了空间,比如有4个数
2 4 7 10001
用桶你就必须得开一个10001的数组,而用HASH只需要开一个长度为4的数组,它们的位置分别为
2%4=2 4%4=0 7%4=3 10001%4=1
在HASH表中表示为
0 1 2 3
4 10001 2 7
明白了吗?其实就是%一个数而已,若%的过程中,这个位置已经有数了,那么就放在它的后面就行了,以此类推。
需要注意的是统计数量,本人的处理方法使用结构体保存数量(即出现相同解的时候)
AC代码
#include<iostream>
#include<cstdio>
using namespace std;
const long long M=1000007;
long long s,x[M];
struct node
{
long long sum,num;
}a[M];
long long h(long long x1)
{
return x1%M;
}
long long dw(long long x)//定位
{
long long i=0,o=h(x);
while(a[(i+o)%M].sum!=0&&a[(i+o)%M].sum!=x&&i<M)
i++;
return (i+o)%M;
}
int main()
{
int n,c;
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++)
{
scanf("%d",&x[i]);
int l=dw(x[i]);
if(a[l].sum==x[i])a[l].num++;//出现次数
else a[l].num=1;
a[l].sum=x[i];//赋值
}
for(int i=1;i<=n;i++)
s+=a[dw(x[i]-c)].num;//累加
cout<<s;
}