洛谷：P1102：A-B数对


洛谷：P1102：A-B数对

Table of Contents

题目

P1102：A-B数对

分析

要解决这道题，需要掌握双指针这个编程思路。

我们来看样例输入，逐步分析如何用双指针法来解题：

输入1：8 3

输入2：2 5 3 7 5 2 4 8

如果按照输入的顺序，从左往右一个一个遍历，那么复杂度会是\(O(N^2)\)。

我们首先要想到的，是排序这个输入。其次，我们应该想得到：排序后，如果随机挑两个数进行A（右数）-B（左数）的操作，其差可以大于、等于、小于3（也就是输入的c）。

  1. 如果太大：说明我们挑选的左边位置（l）太小，需要往右走。
  2. 如果太小：说明我们挑选的右边位置（r）太小，需要往右走。
  3. 如果相等：说明找到一对数。那么r-l就是这个我们需要找的满足条件的数对的个数。将其累加就能得到结果。

为什么可以用r-l一次性统计？

因为根据我们的算法：

  1. l必然指向第一个满足\(s[i]-s[l]=c\)的位置。（25-28行）
  2. r必然指向第一个满足\(s[i]-s[r]\lt c\)的位置。（29-32行）
  3. 所以，r-l这个区间一定满足\(s[i]-s[l]=c\)的条件。

当然，一开始的时候，这两个“指针”要从0开始。

答案

Solution

思考

双指针是很重要的一个概念。请读者认真研究并掌握。

这道题在“集合”这个章节再次出现，用STL后，会更简单、更直观地解决。代码如下：

#include <bits/stdc++.h>
using namespace std;

const int MAX=200'010;

map<int, int> s;
int a[MAX];
int n, c;

int main()
{
    cin>>n>>c;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        s[a[i]]++;
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=s[a[i]-c];
    }

    cout<<ans<<endl;
    return 0;
}

核心：我们用s来存放类似这样的数据：3: 2，表示3这个数字出现了2次。既然题目要求A-B=C这三个数字中的A/B都在集合里，那么可以转换一下思路：遍历集合，每个数字作为A，进行A-C=(B)的操作，看看这样的B在集合中有几个，然后加总就可以了。

上一篇 下一篇