P1102 A-B 数对

算法题思路分享

题目描述

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

输入格式

输入共两行。

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

第二行，第i ii个数为a i a_iai​，数字之间用一个空格隔开，共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。

解题思路

1. 题目大意：给一个长度为 n 的正整数数列和一个固定差值 c，从数列中任取两个不同位置的数，一个作 A，另一个作 B，统计 A−B=c 的取法数。数对按位置区分，数值相同但位置不同也算两对。

2. 常规思路：直接双重循环枚举全部数对，逐个验算差值是否为 c。时间复杂度 O(N²)，n 取最大 2×10⁵ 时约为 4×10¹⁰ 次运算，远超评测机一秒能承受的 10⁸ 量级，必然超时，需要更优的解法。

3. 进阶思路：对 A−B=C 移项，得到 A=B+C。此时 B 一旦取定，A 的取值就唯一确定了，不需要在两类数之间盲目配对。于是解法明确：遍历数列，让每个数轮流作 B，统计 B+C 这个值在数列中出现的次数，每出现一次就构成一对。查询贯穿整个统计过程，必须保证单次查询足够快，这里引入 STL 容器 map：读入阶段记录每个数值的出现次数，之后统计阶段只需按键查询。

4. 实现步骤： 第一步，读入 n 和 c，开一个数组保存数列本体，再开一个 map 计数表，键为数值，值为该数值的出现次数。 第二步，循环读入数列，每读一个数就在表中登记一次，对应次数加一。 第三步，再循环一遍，每个位置的数轮流作 B，把值 B+C 的出现次数累加给 ans。累加的是次数而不是一，该值出现几次就加几。 第四步，输出 ans。

5. 复杂度和一个易错点：map 单次查询 O(log N)，整体时间复杂度 O(N log N)，n 为 2×10⁵ 时轻松通过。易错点在数据范围：当一半的数全是 x、另一半全是 x+C 时，答案达到 10⁵ 乘 10⁵ 即 10¹⁰，而 int 上限只有约 2.1×10⁹，必然溢出，所以全程序使用 long long。

6. 具体的代码实现：

// P1102 A-B 数对#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(0);cin.tie(0);longlongn,c;// n表示数列的元素个数，c表示差值cin>>n>>c;// 定义一个动态数组vector，用于存放数列中的数，数组初始大小为nvector<longlong>a(n);// 定义一个计数表，键为数值，值为该数值的出现次数，用于查询某值出现的次数map<longlong,longlong>cnt;// 依次输入数列中的各个元素for(longlongi=0;i<n;i++){// 存放到数组中cin>>a[i];// 登记进计数表中if(cnt.count(a[i])==0){// 如果此元素是第一次存放，就另开一行，值为0cnt[a[i]]=0;}cnt[a[i]]++;}// 定义一个变量，用于计数：满足 A-B=C 的数对的个数longlongans=0;for(longlongi=0;i<n;i++){// 统计符合A = B + C的个数ans+=cnt[a[i]+c];}// 最后输出anscout<<ans<<'\n';}