双指针洛谷题
时间: 2025-07-31 21:43:56 AIGC 浏览: 25
双指针算法是一种高效的算法技巧,常用于解决数组、字符串、滑动窗口等问题。它通常包含两个指针,一个“快指针”和一个“慢指针”,通过它们的相对移动来解决问题。以下是一些与双指针算法相关的洛谷题目推荐,适合练习和深入理解该算法。
### 1. 洛谷 P1102 A-B 数对
问题描述:给定一个整数数组和一个目标值 $ c $,求所有满足 $ A - B = c $ 的数对 $ (A, B) $ 的个数。
解决思路:可以先对数组进行排序,然后使用双指针技巧来统计符合条件的数对。具体做法是维护两个指针 $ b1 $ 和 $ b2 $,通过比较 $ arr[a] - arr[b1] $ 和 $ arr[a] - arr[b2] $ 与 $ c $ 的关系,移动指针并统计结果。
### 2. 洛谷 P1638 逛画展
问题描述:给定一个画展的时间段和画家的出现顺序,求满足所有画家都出现的最短时间段。
解决思路:使用双指针法(滑动窗口)来寻找满足条件的最小区间。通过左右指针的移动,逐步缩小窗口大小,直到找到满足条件的最小窗口。
### 3. 洛谷 A1147 连续自然数和
问题描述:给定一个自然数 $ m $,找出所有连续自然数序列,使得它们的和等于 $ m $。
解决思路:使用双指针法(滑动窗口)来寻找连续的自然数序列。通过维护一个滑动窗口的左右边界,逐步调整窗口的大小,直到找到符合条件的序列。
### 4. 洛谷 P2872 Fence Repair(类似题目)
问题描述:给定一个数组,要求将数组分割成若干个子数组,使得每个子数组的最大值之和最小。
解决思路:虽然该题的最优解通常使用贪心算法或优先队列,但也可以通过双指针法来实现。通过维护一个滑动窗口,计算窗口内的最大值,并逐步调整窗口大小。
### 5. 洛谷 P1908 逆序对(双指针变种)
问题描述:求一个数组中的逆序对数量。
解决思路:虽然该题通常使用归并排序解决,但也可以通过双指针法的变种来实现。通过维护两个指针,分别指向两个有序子数组,并统计逆序对的数量。
### 示例代码:洛谷 P1102 A-B 数对
```cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, c;
int arr[200020];
int main() {
scanf("%d %d", &n, &c);
for (int i = 1; i <= n; ++i)
cin >> arr[i];
sort(arr + 1, arr + 1 + n); // 对输入的数组进行排序
ll res = 0; // 因为数据使用int会溢出,所以用long long
// 三个指针:快指针a,慢指针b1, b2
for (int a = 1, b1 = 1, b2 = 1; a <= n; ++a) {
while (b1 <= a && arr[a] - arr[b1] >= c)
b1++;
while (b2 <= a && arr[a] - arr[b2] > c)
b2++;
res += b1 - b2;
}
printf("%lld", res);
return 0;
}
```
### 双指针算法的核心思想
双指针算法的核心思想是通过两个指针的移动来解决问题。通常,一个指针作为“快指针”,另一个作为“慢指针”。快指针用于遍历数据,而慢指针用于维护某些条件。通过快慢指针的配合,可以高效地解决许多问题,例如寻找中间元素、滑动窗口等。
阅读全文
相关推荐



















