网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

P1102 A-B 数对

2021/5/2 22:55:00 人评论

洛谷P1102 A-B 数对 题目描述 出题是一件痛苦的事情! 相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 AB Problem,改用 A-B 了哈哈! 好吧,题目是这样的:给出一串数以及一个数字 C,…

洛谷P1102 A-B 数对
题目描述
出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

好吧,题目是这样的:给出一串数以及一个数字 C,要求计算出所有 A - B = C 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式
输入共两行。

第一行,两个整数 N, C。

第二行,N 个整数,作为要求处理的那串数。

输出格式
一行,表示该串数中包含的满足 A - B = C 的数对的个数。

输入输出样例
输入

4 1
1 1 2 3

输出

3

说明/提示
对于 75 % 75\% 75% 的数据, 1 ≤ N ≤ 2000 1 \leq N \leq 2000 1N2000

对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 2 × 1 0 5 1 \leq N \leq 2 \times 10^5 1N2×105

保证所有输入数据都在 32 位带符号整数范围内。

2017/4/29 新添数据两组

解题思路

当然,暴力是一定会TLE的,说明很明确,应该是错3个点

其实一开始我的思路就是一样的,用一个数组压缩,只记录每个数出现的次数就行了,但是实现起来很麻烦,最后才想到用map映射。

#include<iostream>
#include<cstdio> 
#include<map>
using namespace std;
int n, c;
long long ans;
map<int, int> a;
int b[200005];
int main()
{
    ios::sync_with_stdio(false);
    scanf_s("%d%d", &n, &c);
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i];
        a[b[i]]++;    //当前数的个数++ 
    }
    for (int i = 1; i <= n; i++)
    {
        ans += a[b[i] + c];    //答案+=相差为c的数的个数,即a[num[i]+c]位置的数的个数 
    }
    printf("%lld", ans);
    return 0;
}

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?