P1102 A-B数对
题目描述
出题是一件痛苦的事情!
题目看多了也有审美疲劳,于是我舍弃了大家所熟悉的A+B Problem,改用A-B了哈哈!
好吧,题目是这样的:给出一串数以及一个数字C,要求计算出所有A-B=C的数对的个数。(不同位置的数字一样的数对算不同的数对)
输入输出格式
输入格式:
第一行包括2个非负整数N和C,中间用空格隔开。
第二行有N个整数,中间用空格隔开,作为要求处理的那串数。
输出格式:
输出一行,表示该串数中包含的所有满足A-B=C的数对的个数。
输入输出样例
输入样例#1:
4 1 1 1 2 3
输出样例#1:
3
说明
对于73%的数据,N <= 2000;
对于100%的数据,N <= 200000。
所有输入数据都在longint范围内。
2017/4/29新添数据两组
sort排序+模拟84分
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 200100 #define ll long long using namespace std; ll n,c,b,ans,a[N]; ll read() { ll x=,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f; } int main() { n=read(),c=read(),b=; ;i<=n;i++) a[i]=read(); sort(a+,a++n); ;i<=n;i++) for(int j=b;j<i;j++) if(a[i]-a[j]<=c) if(a[i]-a[j]==c) ans++; else break; else b=j; printf("%lld",ans); ; }
84分代码
map AC
#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 200100 #define ll long long using namespace std; map<int,int>m; ll n,c,ans,a[N],maxn; ll read() { ll x=,f=; char ch=getchar(); ;ch=getchar();} +ch-',ch=getchar(); return x*f; } int main() { n=read(),c=read(); ;i<=n;i++) { a[i]=read(); m[a[i]]++; maxn=max(maxn,a[i]); } sort(a+,a++n); ;i<=n;i++) if(a[i]+c>maxn) break; else ans+=m[a[i]+c]; printf("%lld",ans); ; }