(洛谷) P1102A-B 数对

发表于 更新于 分类于 ，

题目背景

出题是一件痛苦的事情！

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

题目描述

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

输入格式

输入共两行。

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
4 1
1 1 2 3

样例输出 #1

1
3

提示

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

对于 100%100\% 的数据，1≤N≤2×1051 \leq N \leq 2 \times 10^5，0≤ai<2300 \leq a_i <2^{30}，1≤C<2301 \leq C < 2^{30}。

2017/4/29 新添数据两组

思路

分析题目可知，对于任意一个 A，均有唯一一个数值 B，满足 A−B=CA - B = C，因此，我们只要用二分查找来查找对于这个数组中的 arr [i]，有多少项满足其值等于对应的值即可。

在 C++ STL（标准模板库）中，upper_bound() 和 lower_bound() 函数是用于对有序容器进行二分查找的常用函数。

lower_bound() 函数接受两个参数：容器的起始和结束迭代器，以及要查找的值。它返回一个指向容器中第一个大于或等于查找值的迭代器，如果容器中所有元素都小于查找值，则返回容器的结束迭代器。例如，如果我们有一个有序的 vector<int> 容器 v，并且要查找值 x，则可以使用以下代码来查找第一个大于或等于 x 的元素：

1
auto it = std::lower_bound(v.begin(), v.end(), x);

upper_bound() 函数的行为与 lower_bound() 函数类似，但它返回的是一个指向容器中第一个大于查找值的迭代器，而不是大于或等于。例如，如果我们有一个有序的 vector<int> 容器 v，并且要查找值 x，则可以使用以下代码来查找第一个大于 x 的元素：

1
auto it = std::upper_bound(v.begin(), v.end(), x);

这两个函数通常用于在有序容器中进行二分查找。它们的时间复杂度为 O (log n)，其中 n 是容器中元素的数量。

我们只要用 std::upper_bound(v.begin(),v.end(),x)−lower_bound(v.begin(),v.end(),x)std::upper\_bound(v.begin(), v.end(), x) - lower\_bound(v.begin(), v.end(), x) 就能得到对应值的项数。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, c;
    long long ans = 0;
    cin >> n >> c;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.begin() + n);
    for (int i = 0; i < n; ++i)
    {
        ans += upper_bound(arr.begin(), arr.begin() + n, arr[i] + c) - lower_bound(arr.begin(), arr.begin() + n, arr[i] + c);
    }
    cout << ans << endl;
    return 0;
}