首页 > 代码库 > 1102 A-B数对
1102 A-B数对
题目描述
出题是一件痛苦的事情！
题目看多了也有审美疲劳，于是我舍弃了大家所熟悉的A+B Problem，改用A-B了哈哈！
好吧，题目是这样的：给出一串数以及一个数字C，要求计算出所有A-B=C的数对的个数。（不同位置的数字一样的数对算不同的数对）
输入输出格式
输入格式：第一行包括2个非负整数N和C，中间用空格隔开。
第二行有N个整数，中间用空格隔开，作为要求处理的那串数。
输出格式：输出一行，表示该串数中包含的所有满足A-B=C的数对的个数。
输入输出样例
输入样例#1：
4 11 1 2 3
输出样例#1：
3
说明
对于73%的数据，N <= 2000；
对于100%的数据，N <= 200000。
所有输入数据都在longint范围内。
2017/4/29新添数据两组
数据更新之后题解里面的的大部分都A不了了，都会W掉第3个点
原因很简单，没有开long long
思路：因为是long long ，所以简单的数组hash肯定是过不了了。
我们可以考虑用map
虽然时间复杂度是nlogn但也勉强可以水过去
我们可以吧A-B==C的式子转换一下，转换成A-C=B
这样用map就方便多了，
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<map> 7 #define lli long long int 8 using namespace std; 9 const lli MAXN=200001;10 lli n,c;11 map<lli,int>mp;12 lli a[MAXN];13 lli read(lli & n)14 {15 char c=‘.‘;lli x=0,flag=0;16 while(c<‘0‘||c>‘9‘)17 {18 c=getchar();19 if(c==‘-‘)flag=1;20 }21 while(c>=‘0‘&&c<=‘9‘)22 {23 x=x*10+(c-48);24 c=getchar();25 }26 if(flag==1)n=-x;27 else n=x;28 }29 int main()30 {31 read(n);read(c);32 for(lli i=1;i<=n;i++)33 {34 read(a[i]);35 mp[a[i]]++;36 } 37 lli ans=0;38 for(lli i=1;i<=n;i++)39 if(mp[a[i]-c]!=0)40 ans=ans+mp[a[i]-c];41 printf("%lld",ans);42 return 0;43 }
1102 A-B数对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。