洛谷P1102 《A-B数对》

二月 01, 2018 1722

普及- 的“水”题

题目地址

提前说明：本题难度为普及-

题目描述

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

输入输出格式

输入格式：

第一行包括2个非负整数N和C，中间用空格隔开。

第二行有N个整数，中间用空格隔开，作为要求处理的那串数。

输出格式：

输出一行，表示该串数中包含的所有满足A-B=C的数对的个数。

输入输出样例

输入输出样例1

input:

1
2
4 1
1 1 2 3

output:

1
3

数据说明

对于73%的数据，N <= 2000；

对于100%的数据，N <= 200000。

所有输入数据都在longint范围内。

原题目2017/4/29新添数据两组

解析

暴力解法

粗略一看，这道题是不是特别水？

只需要用 O(n^2) 的暴力解法不就可以了吗？

​ 枚举A和B，再判断A-B是否为C

但是！

你们Naive，没看见那个N<=200000 吗

这样肯定会TLE的啊喂

测试记录 76分

正确解法

作为C++选手，我们一定要发扬光大Alexander留给我们的STL

于是我们就可以用std::map映射来做这道题目（注意这是**普及-**的题目）

将A-B=C转换为A-C=B，然后找这N个数中有几个B就行了

测试记录 AC

代码实现

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int *arr,n,c;

inline void read(){
  ios::sync_with_stdio(false);
  cin >> n >> c;
  arr = new int[n];
  for (int i = 0;i < n;i++){
    cin >> arr[i];
  }
  return;
}

inline int work(){
  int ans = 0;
  for(int i = 0;i < n;i++)
    for (int j = 0;j < n;j++)
      if ((arr[i] - arr[j] == c)) ans++;
  return ans;
}

int main(int argc, char const *argv[]) {
  read();
  cout << work() << endl;
  return 0;
}

正确解法

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 <cstdio>
#include <map>
using namespace std;
int a[200001];

inline void LetMeAccept(){
  int n,c;
  scanf("%d %d",&n,&c);
  map<int,int> p;
  for(int i = 0;i < n;i++){
    scanf("%d",a + i);
    p[a[i]]++;
  }
  long long ans=0;
  for(int i = 0;i < n;i++)
    ans += p[a[i] + c];
  printf("%lld\n",ans);
}

int main(int argc,char const *argv[]){
    LetMeAccept();
    return 0;
}