double-pointers-queue

双指针

定义

双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。最常见的双指针算法有两种：一种是，在一个序列里边，用两个指针维护一段区间；另一种是，在两个序列里边，一个指针指向其中一个序列，另外一个指针指向另外一个序列，来维护某种次序。
在时间或空间条件有限的情况下使用单向遍历需要消耗大量的时间或者根本无法解决问题，这时候就需要我们使用双指针，通过指针的碰撞判断是否达到条件，从而解决问题。

双指针分为快慢指针和左右指针，左右指针通常在数组有序的情况下使用，快慢指针通常在单向遍历需要消耗大量时间，或者有特定要求限制的情况下使用。

左右指针

左右指针通常在数组有序的情况下，从最小和最大端同时对数组进行处理，对满足特定条件的数组元素进行成对处理，快慢指针逐渐靠拢直至发生碰撞，则遍历完所有数组。

一般左右指针用于寻找某个给定的target值，诸如上述的几数之和，就是通过指针遍历数组找到目标值，这个时候左右指针的优点在于，可以减少一层遍历，极大的降低了时间复杂度。遍历后的数组分别从前后开始寻找，通过与目标值大小的比较每次移动其中一个指针即可。

快慢指针

快慢指针中的快慢即两个指针移动的快慢不同，通过两个指针移动速度的不同，判断数组或链表的长度、是否有环、特定位置的数值等。

在不适用额外空间的情况下，可以通过快慢指针在原有的数组上即时更改，通过双指针可一边执行比较一遍更新数组，起到节约空间的作用。

双指针模板

常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间，比如快排的划分过程
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

for (int i = 0, j = 0; i < n; i++) {
    // j从某一位置开始，不一定是0
    while (j < i && check(i, j))
        j++;
    // 具体问题的逻辑
}

双指针算法的核心思想（作用）：优化

在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法对暴力算法进行优化.

当我们采用朴素的方法即暴力枚举每一种可能的情况，时间复杂度为O(n*n)

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        //具体逻辑
    }
}

而当我们使用双指针算法时通过某种性质就可以将上述O(n*n)的操作优化到O(n)

暴力算法和它优化后的双指针算法有什么区别：

由于具有某种单调性，朴素算法往往能优化为双指针算法。

朴素算法每次在第二层遍历的时候，是会从新开始（j会回溯到初始位置），然后再遍历下去。（假设i是终点，j是起点）,而双指针算法由于具有某种单调性，每次在第二层遍历的时候，不需要回溯到初始位置（单调性），而是在满足要求的位置继续走下去或者更新掉。

模板题

逛画展

逛画展

题目描述

博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。

游客在购买门票时必须说明两个数字，$a$ 和 $b$，代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。

Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。

请求出他购买门票时应选择的 $a,b$，数据保证一定有解。

若存在多组解，输出 $a$ 最小的那组。

输入格式

第一行两个整数 $n,m$，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。

第二行包含 $n$ 个整数 $a_i$，代表画第 $i$ 幅画的名师的编号。

输出格式

一行两个整数 $a,b$。

样例 #1

样例输入 #1

12 5
2 5 3 1 3 2 4 1 1 5 4 3

样例输出 #1

2 7

提示

数据规模与约定

• 对于 $30%$ 的数据，有 $n\le200$，$m\le20$。
• 对于 $60%$ 的数据，有 $n\le10^5$，$m\le103$。
• 对于 $100%$ 的数据，有 $1\leq n\le10^6$，$1 \leq a_i \leq m\le2\times10^3$。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 1000007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
int w[M];
int book[M], ans[M];
int n, m;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    int cnt = 0, mini = INF;
    int a, b, flag = 0;
    for (int l = 1, r = 1; r <= n; r++) {
        ans[w[r]]++;
        if (!book[w[r]]) {
            book[w[r]] = 1;
            cnt++;
            if (cnt == m)
                flag = 1;
        }
        while (ans[w[l]] > 1) {
            ans[w[l]]--;
            l++;
        }
        if (flag && r - l < mini) {
            mini = r - l;
            a = l;
            b = r;
        }
    }
    cout << a << " " << b << endl;
    return 0;
}

[蓝桥杯 2020 省 A1] 整数小拼接

题目描述

给定一个长度为 $n$ 的数组 $A_1,A_2,\cdots,A_n$。你可以从中选出两个数 $A_i$ 和 $A_j$($i\ge j$)，然后将 $A_i$ 和 $A_j$ 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 $A_i$ 和 $A_j$ 的顺序总是被视为 $2$ 种拼法，即便是 $A_i=A_j$ 时。

请你计算有多少种拼法满足拼出的整数小于等于 $K$。

输入格式

第一行包含 $2$ 个整数 $n$ 和 $K$。

第二行包含 $n$ 个整数 $A_1,A_2,\cdots,A_n$。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

4 33
1 2 3 4

样例输出 #1

8

提示

对于 $30%$ 的评测用例 $1\le n\le1000$，$1\le k\le10^8$，$1\le A_i\le10^4$。

对于所有评测用例，$1\le n\le10^5$，$1\le k\le10^{10}$，$1\le A_i\le10^9$。

蓝桥杯 2020 第一轮省赛 A 组 H 题。

AC代码

folding code

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1000007
#define INF 0x3f3f3f3f
#define mod 99999997
#define ll long long
#define db double
#define pii pair<int, int>
ll n, k;
ll a[N], ans;
ll calc(ll num) {
    ll tot = 1;
    while (num)
        num /= 10, tot *= 10;
    return tot;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> k;
    ll l = 1, r = n;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (ll i = 1; i <= n; i++) {
        if (r < i)
            break;
        ll tot = calc(a[i]);
        while (r > i && a[r] * tot + a[i] > k)
            r--;
        ans += r - i;
    }
    for (int i = n; i; i--) {
        if (i < l)
            break;
        ll tot = calc(a[i]);
        while (l < i && a[l] * tot + a[i] <= k)
            l++;
        if (l > 0)
            l--;
        ans += l;
    }
    cout << ans;
    return 0;
}

[蓝桥杯 2022 省 B] 统计子矩阵

题目描述

给定一个 $N \times M$ 的矩阵 $A$，请你统计有多少个子矩阵 (最小 $1 \times 1$, 最大 $N \times M)$ 满足子矩阵中所有数的和不超过给定的整数 $K$。

输入格式

第一行包含三个整数 $N, M$ 和 $K$。

之后 $N$ 行每行包含 $M$ 个整数, 代表矩阵 $A$。

输出格式

一个整数代表答案。

样例 #1

样例输入 #1

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

样例输出 #1

19

提示

【样例说明】

满足条件的子矩阵一共有 $19$，包含:

大小为 $1 \times 1$ 的有 $10$ 个。

大小为 $1 \times 2$ 的有 $3$ 个。 大小为 $1 \times 3$ 的有 $2$ 个。

大小为 $1 \times 4$ 的有 $1$ 个。

大小为 $2 \times 1$ 的有 $3$ 个。

【评测用例规模与约定】

对于 $30 %$ 的数据, $N, M \leq 20$.

对于 $70 %$ 的数据, $N, M \leq 100$.

对于 $100 %$ 的数据, $1 \leq N, M \leq 500,0 \leq A_{i j} \leq 1000,1 \leq K \leq 2.5\times10^8$.

蓝桥杯 2022 省赛 B 组 F 题。

AC代码

folding code

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define mod 99999997
#define ll long long
#define db double
#define pii pair<int, int>
ll n, m, K, cnt;
ll ma[N][N], s[N][N], b[N];
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n >> m >> K;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> ma[i][j];
            s[i][j] = s[i - 1][j] + ma[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int k = i; k <= n; k++) {
            for (int j = 1; j <= m; j++) {
                b[j] = s[k][j] - s[i - 1][j];
            }
            ll now = 0;
            for (int l = 1, r = 1; r <= m; r++) {
                now += b[r];
                if (now <= K) {
                    cnt += r - l + 1;
                } else {
                    while (now > K) {
                        now -= b[l];
                        l++;
                    }
                    cnt += r - l + 1;
                }
            }
        }
    }
    cout << cnt;
    return 0;
}