csp信奥赛C++标准模板库STL案例应用9

csp信奥赛C++标准模板库STL案例应用9

map实践

题目背景

出题是一件痛苦的事情！

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

题目描述

给出一串正整数数列以及一个正整数C CC，要求计算出所有满足A − B = C A - B = CA−B=C的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数N , C N,CN,C。

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

输出格式

一行，表示该串正整数中包含的满足A − B = C A - B = CA−B=C的数对的个数。

输入输出样例 1

输入 1

4 1 1 1 2 3

输出 1

3

说明/提示

对于75 % 75\%75%的数据，1 ≤ N ≤ 2000 1 \leq N \leq 20001≤N≤2000。

对于100 % 100\%100%的数据，1 ≤ N ≤ 2 × 10 5 1 \leq N \leq 2 \times 10^51≤N≤2×105，0 ≤ a i < 2 30 0 \leq a_i <2^{30}0≤ai​<230，1 ≤ C < 2 30 1 \leq C < 2^{30}1≤C<230。

核心思路

题目要求找出所有满足 A - B = C 的数对（A 和 B 均来自给定数列，且不同位置的相同数字算不同数对）。由于 C ≥ 1，因此 A 和 B 必然不相等（A > B）。
基本思路为：对于每个数字 B，其对应的 A = B + C。统计每个数字出现的次数，然后遍历每个 B，累加对应的 A 出现的次数即可。

算法步骤

1. 读取输入：读取整数个数 N、差值 C，以及 N 个正整数。
2. 频率统计：使用map<long long, long long>统计每个数字在数列中出现的次数。
3. 遍历计算：对于每个数字 B（即数列中的每个元素），计算 A = B + C，若 A 存在于map中，则将其出现次数累加到结果中。
4. 输出结果：输出最终累加的结果。

时间复杂度与空间复杂度

• 时间复杂度：O(N log N)。主要开销在于map的插入和查找操作（每次 O(log N)），共进行 2N 次操作（N 次插入和 N 次查找）。
• 空间复杂度：O(N)。用于存储数组和map。

关键点说明

• 使用map存储数字频率，便于快速查找。
• 由于 C ≥ 1，A 和 B 不可能相同，因此无需考虑同一元素重复使用的情况。
• 结果cnt使用long long类型，防止计数溢出（最大数对数量可达 N² 级别）。
• 查找时使用m.find(t) != m.end()判断是否存在，避免不必要的默认构造。

代码实现

#include<bits/stdc++.h>usingnamespacestd;longlongn,c,a[200010],cnt;// n: 数字个数, c: 差值, a: 存储数列的数组, cnt: 结果计数器map<longlong,longlong>m;// 映射：数字 -> 该数字在数列中出现的次数intmain(){// 读入 n 和 ccin>>n>>c;// 读入数列并统计每个数字的出现次数for(inti=1;i<=n;i++){cin>>a[i];m[a[i]]++;// 对应数字的出现次数加 1}// 遍历每个数字作为 Bfor(inti=1;i<=n;i++){longlongt=a[i]+c;// 计算对应的 A = B + c// 检查 A 是否存在于数列中if(m.find(t)!=m.end()){cnt+=m[t];// 若存在，则累加 A 的出现次数}}// 输出满足条件的数对个数cout<<cnt;return0;}

功能分析

1. 输入处理：第一行读入 N 和 C，第二行读入 N 个正整数存入数组a，同时用map记录频率。
2. 频率统计：map的键为数字，值为该数字在数列中出现的次数。例如，数列[1,1,2,3]对应的map为{1:2, 2:1, 3:1}。
3. 数对计数：
   • 对于每个数字 B（如 B=1），计算 A = B + C（如 C=1 时 A=2）。
   • 查找 A 是否在map中（如 A=2 出现 1 次），若存在则将 A 的出现次数累加到cnt。
   • 遍历所有 B 后，cnt即为总数对个数。
4. 输出结果：直接输出cnt。

示例验证

以样例为例：

输入： 4 1 1 1 2 3

• 频率统计：1 出现 2 次，2 出现 1 次，3 出现 1 次。
• 遍历：
  • B=1, A=2：出现 1 次 → cnt+=1
  • B=1, A=2：出现 1 次 → cnt+=1
  • B=2, A=3：出现 1 次 → cnt+=1
  • B=3, A=4：无对应 → 不加
• 输出：3

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

• 2025 csp-j 复赛真题及答案解析（最新更新）
• 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
• 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
• 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
• 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
• 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
• 2020 ~ 2024 csp 复赛真题题单及题解
• 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
• 2021 ~ 2024 csp-s 初赛高频考点解析
• 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
• 2024 csp-j 初赛真题及答案解析
• 2025 csp-j 初赛真题及答案解析（最新更新）
• 2025 csp-s 初赛真题及答案解析（最新更新）
• 2025 csp-x (山东)初赛真题及答案解析(最新更新)
• 2025 csp-x (江西)初赛真题及答案解析(最新更新)
• 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

• 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}