双指针的两道题目题解
本帖最后由 王逗比666 于 2023-4-24 17:50 编辑这次用了@twilight6大佬的新更新的转换器
可惜的是数学公式限于各种原因无法实现转换（其实有的markdown引擎也渲染不了）
twilight6大佬保留了显示语言的功能，但是修复了将'>'第一个空格改成字符的问题之后我的引用块中的内容就开始出现`>`了，但是我觉得这不算bug，因为在给出的对照表中，引用块是`>`而不是我习惯的'>>'，所以应该算是我的语法不规范的问题(所以上次没有发现这个bug是因为bug把我本来应该多出来的`>`吞掉了{:10_250:})
除此之外体验还不错，当然这里还是给出.md文件，供有需求的读者阅读{:10_256:}
P1102 A-B 数对
A-B 数对
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 $N,C$。
第二行，$N$ 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。
样例 #1
样例输入 #1
4 1
1 1 2 3
样例输出 #1
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$的个数，两者相减就是答案
c++
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
int n, c;
cin >> n >> c;
int a;
for(int i = 0; i < n; i++)
cin >> a;
sort(a, a + n);
int p = 0, q = 0, ans = 0;
for(int i = 0; i < n; i++) {
while(a - a <= c && p < n) p++;
while(a - a < c && q < n) q++;
ans += p - q;
}
cout << ans << endl;
return 0;
}
> 另外有个问题是同样的代码我在洛谷提交的时候花的时间很短，但是在xyxy-scp.cn上提交后却花了1000ms，不知道是评测机的问题还是数据的问题。
*
P8667 [蓝桥杯 2018 省 B] 递增三元组
[蓝桥杯 2018 省 B] 递增三元组
题目描述
给定三个整数数组 $A = $，$B = $，$C = $。
请你统计有多少个三元组 $(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
3
1 1 1
2 2 2
3 3 3
样例输出 #1
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$的个数就可以了
>当然这道题也需要排序
c++
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main(void) {
ll n;
cin >> n;
int a, b, c;
for(ll i = 0; i < n; i++)
cin >> a;
for(ll i = 0; i < n; i++)
cin >> b;
for(ll i = 0; i < n; i++)
cin >> c;
sort(a, a + n); sort(b, b + n); sort(c, c + n);
ll ans = 0, p = 0, q = 0;
for(ll i = 0 ; i < n; i++) {
while(a < b && p < n) p++;
while(c <= b && q < n) q++; //在这里我们找的是c中小于等于a的元素的个数，那么我们要求的c中大于a的个数即为n - q
ans += p * (n - q);
}
cout << ans << endl;
return 0;
}
你是复制的吧 sfqxx 发表于 2023-4-24 18:16
你是复制的吧
我自己写的，包括我上一个帖子也是，只不过我上一个发布在dbywsc.github.io上，这个没有发，我的Md源文件属性也有文件的编辑时间 王逗比666 发表于 2023-4-24 18:18
我自己写的，包括我上一个帖子也是，只不过我上一个发布在dbywsc.github.io上，这个没有发，我的Md源文件 ...
m原来如此
页:
[1]