双指针简介
之前做CF660C时接触过，但是这个思想感觉挺炸裂的（
双指针也叫尺取法，通常使用两个变量保存区间的两个端点，交替推进两个端点直到得出答案，Codeforces中显示它的算法名称叫做"two pointers". 直译成中文的话叫双指针法。
例题
[蓝桥杯 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 题。
题解
本题直接暴力搜索，可以拿30分左右。对于70%的数据，我们可以使用二维前缀和，这样每次查询的矩阵的数字之和时间复杂度可以变成$O(1)$，但是仍然要枚举区间的4个端点，还是会TLE。
正解可以用双指针来做，可以优化掉一维，只需要枚举两个纵坐标y1,y2，然后将y1~y2内的横坐标相同的一列数字视为一个整体，使用双指针。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
long long a[maxn][maxn] = {}, b[maxn][maxn] = {}, K, ans = 0, num[maxn] = {};
int m, n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> K;
for (register int i = 1; i <= n; i++)
for (register int j = 1; j <= m; j++)
cin >> a[i][j];
// 预处理二维前缀和数组b
for (register int i = 1; i <= n; i++)
for (register int j = 1; j <= m; j++)
b[i][j] = a[i][j] + b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
for (register int i = 1; i <= n; i++)
for (register int j = i; j <= n; j++)
{
int l = 0, r = 1;
for (register int k = 1; k <= m; k++)
num[k] = b[j][k] - b[i - 1][k] - b[j][k - 1] + b[i - 1][k - 1] + num[k - 1];
// 将横坐标相同的一列数字视压缩为一个数字，方便双指针操作
for (; r <= m; r++) // 双指针
{
while (num[r] - num[l] > K)
l++;
ans += r - l;
}
}
cout << ans << endl;
return 0;
}[USACO17DEC]Haybale Feast G
题面翻译
题意：给定2个由N个数字组成的数列$F$,$S$,需要找到使得$\sum_{k=i}^{j}F_k\geqslant M$的$i$,$j$并输出在所有满足条件的$i$,$j$中，$max(Si,S{i+1},...S_{j-1},S{j})$的最小值。
翻译贡献者：Il_ItzABC_lI
题目描述
Farmer John is preparing a delicious meal for his cows! In his barn, he has $N$ haybales ($1 \le N \le 100,000$). The $i$th haybale has a certain flavor $F_i$ ($1 \le F_i \le 10^9$) and a certain spiciness $S_i$ ($1 \le S_i \le 10^9$).
The meal will consist of a single course, being a contiguous interval containing one or more consecutive haybales (Farmer John cannot change the order of the haybales). The total flavor of the meal is the sum of the flavors in the interval. The spiciness of the meal is the maximum spiciness of all haybales in the interval.
Farmer John would like to determine the minimum spiciness his single-course meal could achieve, given that it must have a total flavor of at least $M$ ($1 \le M \le 10^{18}$).
输入格式
The first line contains the integers $N$ and $M$, the number of haybales and the minimum total flavor the meal must have, respectively. The next $N$ lines describe the $N$ haybales with two integers per line, first the flavor $F$ and then the spiciness $S$.
输出格式
Please output the minimum spiciness in a single course meal that satisfies the minimum flavor requirement. There will always be at least one single-course meal that satisfies the flavor requirement.
样例 #1
样例输入 #1
5 10
4 10
6 15
3 5
4 9
3 6样例输出 #1
9题解
这道题好像可以二分答案
题目要求先求出最大的$\sum_{k=i}^{j}F_k\geqslant M$的$i$,$j$，我们可以用双指针$O(n)$扫描一遍所有符合条件的$i$,$j$，然后使用线段树维护S数组的最大值，对每个符合条件的$i$,$j$进行查询，然后输出其中的最小值即可。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100005;
#define root 1, n, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
int z[maxn << 2] = {}, cnt = 0;
// a为前缀和数组
int n;
long long m, f[maxn] = {}, a[maxn] = {};
int s[maxn] = {};
inline int max(int a, int b)
{
return a > b ? a : b;
}
inline void update(int rt)
{
z[rt] = max(z[rt << 1], z[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
if (l == r)
{
z[rt] = s[++cnt];
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
update(rt);
}
int find(int l, int r, int rt, int findl, int findr)
{
if (findl == l and findr == r)
{
return z[rt];
}
int mid = (l + r) >> 1;
if (findl <= mid)
{
if (findr > mid)
return max(find(lson, findl, mid), find(rson, mid + 1, findr));
return find(lson, findl, findr);
}
return find(rson, findl, findr);
}
vector<int> ans;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (register int i = 1; i <= n; i++)
{
cin >> f[i] >> s[i];
a[i] += a[i - 1] + f[i];
}
build(root); //建树
int l = 0, r = 1;
while (l <= n) // 双指针
{
if (a[r] - a[l] >= m)
{
// 找到符合条件的区间就使用线段树查询
int x = find(root, l + 1, r);
ans.push_back(x);
l++;
}
else
{
if (r <= n)
r++;
else
l++;
}
}
int minn = 2147483647;
for (auto i : ans)
minn = min(i, minn);
cout << minn;
}逛画展
题目描述
博览馆正在展出由世上最佳的 $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\le10^3$。
- 对于 $100\%$ 的数据，有 $1\leq n\le10^6$，$1 \leq a_i \leq m\le2\times10^3$。
题解
这题与之前的题不太一样，要检查是否逛完了全部画师的作品，一开始我写的是暴力扫一遍来check，结果TLE了一个点。其实可以开一个变量cnt来记录当前看的画师的个数数。如果有画师的作品数到了零或者从零变为一，直接更新cnt即可。
#include <iostream>
#include <fstream>
using std::cout;
using std::cin;
const int maxn = 1000005;
int n, m, a[maxn] = {}, vis[maxn] = {};
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (register int i = 1; i <= n; i++)
{
cin >> a[i];
}
vis[a[1]]++;
int min_ans = 2147483647, minl, minr;
int l = 1, r = 1, cnt = 1;
while (l <= n)
{
if (cnt == m)
{
if (r - l + 1 < min_ans)
{
min_ans = r - l + 1;
minl = l;
minr = r;
}
if (--vis[a[l++]] == 0)
cnt--;
continue;
}
if (r < n)
{
r++;
if (vis[a[r]] == 0)
cnt++;
vis[a[r]]++;
}
else if (-vis[a[l++]] == 0)
cnt--;
}
cout << minl << " " << minr;
return 0;
}
Comments NOTHING