本文主要是介绍P1102 A-B 数对 （非二分，不开龙永远的痛，用map解决），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
可是我真的会伤心
题目链接
思路：1.本来想的是暴力，两层循环模拟每个数。
2.后来想先把每个数字的个数求出来放在数组nums【】中，并把不重复的数字存到数组b，再两层循环b数组应该时间复杂度会好些，如果b数组中的两个数满足条件，则把nums【i】*nums【b】加入到答案ans中。
暴力代码：76分
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;int n,c;
long long a[1000010];
int cnt;int main()
{scanf("%d%d",&n,&c);for(int i=0;i<n;i++){scanf("%lld",&a[i]);}sort(a,a+n);//先思考暴力的//可以用窗口 for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){if(a[j] - a[i] == c){cnt++;}}} printf("%d",cnt);return 0;
}结果：
尝试代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;int n,c;
long long a[1000010];
long long b[1000010];int nums[1000010];
int cnt;
int t;int main()
{scanf("%d%d",&n,&c);for(int i=0;i<n;i++){scanf("%lld",&a[i]);}sort(a,a+n);nums[a[0]] = 1;b[0] = a[0];//找出每个数对应的个数，如果它减取前面一个数等于c就直接加上他的个数for(int i=1;i<n;i++){if(a[i] != a[i-1]){t++;nums[a[i]] ++;b[t] = a[i];}else nums[a[i]] ++;}
// for(int i=0;i<=t;i++){
// cout<<b[i]<<" ";
// }
// cout<<endl;// for(int i=0;i<100;i++){
// cout<<nums[i]<<" ";
// }
// cout<<endl;for(int i=0;i<t;i++){for(int j=i+1;j<=t;j++){if(b[j] - b[i] == c){cnt += nums[b[j]] * nums[b[i]];}}}printf("%d",cnt);return 0;} 结果：
代码3：不开龙永远的痛
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;long long n,c;
long long a[1000010];
long long b[1000010];long long nums[1000010];
long long cnt;
long long t;int main()
{scanf("%lld%lld",&n,&c);for(int i=0;i<n;i++){scanf("%lld",&a[i]);}sort(a,a+n);nums[a[0]] = 1;b[0] = a[0];//找出每个数对应的个数，如果它减取前面一个数等于c就直接加上他的个数for(int i=1;i<n;i++){if(a[i] != a[i-1]){t++;nums[a[i]] ++;b[t] = a[i];}else nums[a[i]] ++;}
// for(int i=0;i<=t;i++){
// cout<<b[i]<<" ";
// }
// cout<<endl;// for(int i=0;i<100;i++){
// cout<<nums[i]<<" ";
// }
// cout<<endl;for(int i=0;i<t;i++){for(int j=i+1;j<=t;j++){if(b[j] - b[i] == c){cnt += nums[b[j]] * nums[b[i]];}}}printf("%lld",cnt);return 0;} 结果：92分
AC代码：用map
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int n,c;
int a[200010];
long long ans;
map<int, int> m;//map是映射,map<A,B> 字母A对应个数B
int main()
{scanf("%d%d",&n,&c);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);m[a[i]] ++;}for(int i = 1; i <= n; i++){ans += m[a[i] + c];}printf("%lld",ans);return 0;
} 这篇关于P1102 A-B 数对 （非二分，不开龙永远的痛，用map解决）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
