P1102. A-B 数对

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 485 阅读时长 ≈ 2 分钟

考点

  • 二分
  • 双指针
  • 排列组合

题解

见思路

思路

乘法原理

换个角度看，题目实际上是问你B + C = A的数对个数，

且题目规定C不为0，那么就不需要考虑B等于A的特殊情况，

由于不同位置的数字一样的数对算不同的数对，直接记录B与A的个数，符合条件的两者个数相乘即可，

为了防止计算重复，应从小到大找；记得开long long！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, c, x;
map<int, int> mp;

int main() {
  ll ans = 0;
  cin >> n >> c;
  for (int i = 0; i < n; ++i) cin >> x, ++mp[x];
  for (auto i : mp) {
    if (mp.count(i.first + c)) ans += 1ll * i.second * mp[i.first + c];
  }
  cout << ans;
  return 0;
}

二分

根据a = b + c，排序后枚举b，以二分查找的形式得到满足条件的a个数，累加即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LEN = 2e5 + 50;
int n, c, x, arr[LEN];

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

双指针

根据a - c = b，排序后可通过枚举a来得到b的值，且b一定小于a；所以用双指针来维护b出现的区间，

左边界arr[l]为第一个小于等于b，右边界arr[r]为第一个大于b，对于b来说是左闭右开区间，

这样一来，如果arr[l] == b，那么r - l显然就是b的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LEN = 2e5 + 50;
int n, l, r, c, arr[LEN];

int main() {
  ll ans = 0;
  cin >> n >> c;
  for (int i = 0; i < n; ++i) cin >> arr[i];
  sort(arr, arr + n);
  for (int i = 0; i < n; ++i) {
    int a = arr[i], b = a - c;
    while (l < n && b > arr[l]) ++l;
    while (r < n && arr[r] <= b) ++r;
    if (arr[l] == b) ans += r - l;
  }
  cout << ans;
  return 0;
}