双指针的两道题目题解

王逗比666

这次用了@twilight6大佬的新更新的转换器
可惜的是数学公式限于各种原因无法实现转换（其实有的markdown引擎也渲染不了）
twilight6大佬保留了显示语言的功能，但是修复了将'>'第一个空格改成字符的问题之后我的引用块中的内容就开始出现`>`了，但是我觉得这不算bug，因为在给出的对照表中，引用块是`>`而不是我习惯的'>>'，所以应该算是我的语法不规范的问题(所以上次没有发现这个bug是因为bug把我本来应该多出来的`>`吞掉了)

除此之外体验还不错，当然这里还是给出.md文件，供有需求的读者阅读

P1102 A-B 数对
A-B 数对

题目背景

出题是一件痛苦的事情！

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

题目描述

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

输入格式

输入共两行。

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

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

输出格式

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

样例 #1

样例输入 #1

1. 
   
2. 4 1
   
3. 1 1 2 3
   

复制代码

样例输出 #1

1. 
   
2. 3
   

复制代码

提示

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

对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$,$1 \leq C < 2^{30}$。

2017/4/29 新添数据两组

> 上次遗漏的题,有一说一用双指针真简单
> 值得注意的是我们用双指针时也要先排序
> 对于这道题我们只需要用两个指针p和q分别枚举，p用来计算$a_p - a_i \leq c$的个数，q用来计算$a_q - a_i < c$的个数，两者相减就是答案

1. 
   
2. c++
   
3.     #include <iostream>
   
4.     #include <algorithm>
   
5. 
   
6.     using namespace std;
   
7. 
   
8.     int main(void) {
   
9.         int n, c;
   
10.         cin >> n >> c;
    
11. 
    
12.         int a[n];
    
13.         for(int i = 0; i < n; i++)
    
14.             cin >> a[i];
    
15.         sort(a, a + n);
    
16. 
    
17.         int p = 0, q = 0, ans = 0;
    
18.         for(int i = 0; i < n; i++) {
    
19.             while(a[p] - a[i] <= c && p < n) p++;
    
20.             while(a[q] - a[i] < c && q < n) q++;
    
21.             ans += p - q;
    
22.         }
    
23. 
    
24.         cout << ans << endl;
    
25.         
    
26.         return 0;
    
27.     }
    

复制代码

> 另外有个问题是同样的代码我在洛谷提交的时候花的时间很短，但是在xyxy-scp.cn上提交后却花了1000ms，不知道是评测机的问题还是数据的问题。

*
P8667 [蓝桥杯 2018 省 B] 递增三元组
[蓝桥杯 2018 省 B] 递增三元组

题目描述

给定三个整数数组 $A = [A_1, A_2,\cdots, A_N]$，$B = [B_1, B_2,\cdots, B_N]$，$C = [C_1, C_2,\cdots,C_N]$。

请你统计有多少个三元组 $(i, j, k)$ 满足：
1. $1 \le i, j, k \le N$  
2. $A_i < B_j < C_k$

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $ A_1, A_2,\cdots, A_N$。

第三行包含 $N$ 个整数 $ B_1, B_2,\cdots, B_N$。

第四行包含 $N$ 个整数 $ C_1, C_2,\cdots, C_N$。

输出格式

一个整数表示答案

样例 #1

样例输入 #1

1. 
   
2. 3
   
3. 1 1 1
   
4. 2 2 2
   
5. 3 3 3
   

复制代码

样例输出 #1

1. 
   
2. 27
   

复制代码

提示

对于 $30\%$ 的数据，$1 \le N \le 100$。

对于 $60\%$ 的数据，$1 \le N \le 1000$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le A_i, B_i, C_i \le 10^5$。

>最开始不知道啥是三元组迷茫了好一阵，后来发现其实它只是在找对于每一个$b_i$，数列$a$中小于它的元素和数列$c$中大于它的元素，每三个满足条件的$a_i, b_i, c_i$都算一个满足条件的三元组，所以我们只需要将满足条件的&a_i&的个数乘以满足条件的$b_i$的个数就可以了
>当然这道题也需要排序

1. 
   
2. c++
   
3.     #include <iostream>
   
4.     #include <algorithm>
   
5. 
   
6.     #define ll long long
   
7. 
   
8.     using namespace std;
   
9. 
   
10.     int main(void) {
    
11.         ll n;
    
12.         cin >> n;
    
13.         int a[n], b[n], c[n];
    
14. 
    
15.         for(ll i = 0; i < n; i++)
    
16.             cin >> a[i];
    
17. 
    
18.         for(ll i = 0; i < n; i++)
    
19.             cin >> b[i];
    
20. 
    
21.          for(ll i = 0; i < n; i++)
    
22.             cin >> c[i];
    
23. 
    
24.         sort(a, a + n); sort(b, b + n); sort(c, c + n);
    
25. 
    
26.         ll ans = 0, p = 0, q = 0;
    
27.         for(ll i = 0 ; i < n; i++) {
    
28.             while(a[p] < b[i] && p < n) p++;
    
29.             while(c[q] <= b[i] && q < n) q++;   //在这里我们找的是c中小于等于a[i]的元素的个数，那么我们要求的c中大于a[i]的个数即为n - q
    
30. 
    
31.             ans += p * (n - q);
    
32.         }
    
33. 
    
34.         cout << ans << endl;
    
35. 
    
36.         return 0;
    
37.     }
    

复制代码

sfqxx

你是复制的吧

王逗比666

sfqxx 发表于 2023-4-24 18:16
你是复制的吧

我自己写的，包括我上一个帖子也是，只不过我上一个发布在dbywsc.github.io上，这个没有发，我的Md源文件属性也有文件的编辑时间

sfqxx

王逗比666 发表于 2023-4-24 18:18
我自己写的，包括我上一个帖子也是，只不过我上一个发布在dbywsc.github.io上，这个没有发，我的Md源文件 ...

m原来如此