洛谷P1102 A-B 数对（C++代码讲解）

本文主要是介绍洛谷P1102 A-B 数对（C++代码讲解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目

题目描述

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

输入格式

输入共两行。

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

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

输出格式

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

输入输出样例

输入 #1:

4 1
1 1 2 3

输出 #1:

3

说明/提示

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

对于 100%100% 的数据，1≤N≤2×10^5，0≤ai​<2^30，1≤C<2^30。

2.具体思路

我一开始的思路：

1. 先把数组按从小到大的顺序排好序；
2. 然后对数组进行遍历，每次使用二分查找找出数组中是否存在一个数等于 当前位置数 + C，如果找到那么记录这个数的位置（因为我们不知道是否存在多个相同的数，在题目中和相同的数不同的位置组成的数对也是算不同的数对），然后向左和向右查找是否存在相同的数。
3. 每次找一个满足要求的数那么数对数就加1。

错误代码：

#include <iostream>
#include <algorithm>
#define MAX 200000using namespace std;int main()
{int n;long long c;cin >> n >> c;long long num[MAX] = {0};int i;for( i = 0; i < n; i++){cin >> num[i];}sort( num, num + n);int biao = -1;long long count = 0;for( i = 0; i < n; i++){long long t = num[i] + c;// 因为我们把数按从小到大排好序了，要找到比num[i]大的数只能从i后面开始找int low = i, high = n;while( low <= high ){int mid = low + (high - low) / 2;if( num[mid] == t ){biao = mid;count++;break;}else if( num[mid] > t ){high = mid - 1;}else{low = mid + 1;}}if( biao == -1 ){continue;}for( int j = biao - 1; j >= 0; j--){if( num[j] == t ){count++;}else{break;}}for( int j = biao + 1; j < n; j++){if( num[j] == t ){count++;}else{break;}}}cout << count;return 0;
}

这个代码我提交的时候是第三个测试点超时，当时我就在想为什么这样还会超时，然后我发现可能是我用 sort函数 排序和 循环嵌套 导致的。所以我们要避免这种情况。

改正思路：

1. 不需要对数组进行排序，也不用二分法查找目标元素，我们可以使用 map 关联容器去记录该数字是否存在和出现过几次；
2. 每次我们输入一个数，我们就让它在map中对应键的值加1；
3. 最后我们只需要遍历一遍数组，查找该数是否在map中存在，如果存在数对数就加上对应键的值就ok啦。

正确代码：

#include <iostream>
#include <map>#define MAX 200001using namespace std;int main()
{int n, i;long long c;cin >> n >> c;long long num[MAX] = {0};map<long long, long long> number;for( i = 0; i < n; i++){cin >> num[i];number[num[i]]++;}long long count = 0;for( i = 0; i < n; i++){int t = num[i] + c;count += number[t];}cout << count;return 0;
}

改正后的代码不仅更简洁了，而且效率高了很多。

这篇关于洛谷P1102 A-B 数对（C++代码讲解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---