P1102 A-B 数对

╰半夏微凉° 2023-01-18 09:18 90阅读 0赞

**[洛谷P1102 A-B 数对][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 1≤N≤2000。

对于  100 % 100\\% 100% 的数据， 1 ≤ N ≤ 2 × 1 0 5 1 \\leq N \\leq 2 \\times 10^5 1≤N≤2×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;
    }

[P1102 A-B]: https://www.luogu.com.cn/problem/P1102

发表评论取消回复

表情：

评论列表（有 0 条评论，90人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷---P1102 A-B 数对---双指针算法

> 题目链接： > [P1102 A-B 数对][P1102 A-B] > 题目描述： > ![在这里插入图片描述][096c83e558174a7da38d661

小咪咪/ 2024年03月26日 12:41/ 0 赞/ 46 阅读

相关 p2p视频通话和p2p语音对讲的实现

qq视频聊天和语音聊天功能是我们日常生活中经常使用到的功能。如果我们要实现手机与智能摄像头, 可视门铃, 可视猫眼等智能家居的视频对讲功能，如果以前没有接触过这些方面，难度和复

小灰灰/ 2024年03月25日 20:44/ 0 赞/ 57 阅读

相关蓝桥杯算法训练 ALGO-141 P1102

算法训练 P1102 时间限制：1.0s 内存限制：256.0MB 　　定义一个学生结构体类型student，包括4个字段，姓名、性别、年龄和成绩。然后在主函数中定义一个结

左手的ㄟ右手/ 2023年10月06日 09:39/ 0 赞/ 38 阅读

相关 P1102 A-B 数对

[洛谷P1102 A-B 数对][P1102 A-B] 题目描述出题是一件痛苦的事情！相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Probl

╰半夏微凉°/ 2023年01月18日 09:18/ 0 赞/ 91 阅读

相关 P1102 A-B 数对（加深对lower_bound 和upper_bound的理解）

[传送门][Link 1] 直接暴力，两个for循环， 2 ∗ 1 0 5 2\10^5 2∗105爆炸 2021/3/20 疑问：`ans += ((upper_b

妖狐艹你老母/ 2022年11月11日 06:17/ 0 赞/ 107 阅读

相关蓝桥杯算法训练 P1102

![这里写图片描述][SouthEast] PS：根据题目要求从小到大输出，如果相同则保留原来的输入顺序，由此使用插入排序最为简便。 import java.uti

╰+哭是因爲堅強的太久メ/ 2022年05月31日 00:17/ 0 赞/ 207 阅读

相关使用 ab 对网站进行压力测试

概述这是 Apache 自带的一个网站压力测试工具，是 ApacheBench 的缩写，我们可以使用这个工具来对我们的网站进行压力测试。安装在 Ubuntu 上要安

╰半橙微兮°/ 2022年03月28日 15:54/ 0 赞/ 227 阅读

相关 P2421 A-B数对（增强版）

题目背景 woshiren在洛谷刷题，感觉第一题：求两数的和(A+B Problem)太无聊了，于是增加了一题：A-B Problem，难倒了一群小朋友，哈哈。题目

蔚落/ 2021年12月12日 13:59/ 0 赞/ 133 阅读

相关 P1025-数的划分

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

痛定思痛。/ 2021年11月09日 07:42/ 0 赞/ 269 阅读

相关 P1908-逆序对

1 include <bits/stdc++.h> 2 using namespace std; 3 define _for(i,a,b) for(

喜欢ヅ旅行/ 2021年11月09日 07:40/ 0 赞/ 319 阅读