双指针的两道题目题解

王逗比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

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[n];
        for(int i = 0; i < n; i++)
            cin >> a[i];
        sort(a, a + n);

        int p = 0, q = 0, ans = 0;
        for(int i = 0; i < n; i++) {
            while(a[p] - a[i] <= c && p < n) p++;
            while(a[q] - a[i] < c && q < n) q++;
            ans += p - q;
        }

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

> 另外有个问题是同样的代码我在洛谷提交的时候花的时间很短，但是在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

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[n], b[n], c[n];

        for(ll i = 0; i < n; i++)
            cin >> a[i];

        for(ll i = 0; i < n; i++)
            cin >> b[i];

         for(ll i = 0; i < n; i++)
            cin >> c[i];

        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[p] < b[i] && p < n) p++;
            while(c[q] <= b[i] && q < n) q++;   //在这里我们找的是c中小于等于a[i]的元素的个数，那么我们要求的c中大于a[i]的个数即为n - q

            ans += p * (n - q);
        }

        cout << ans << endl;

        return 0;
    }

sfqxx

你是复制的吧

王逗比666

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

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

sfqxx

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

m原来如此