双指针算法复习笔记
撰文原因：恢复训练状态
今天复习一下双指针算法
双指针算法，又名尺取法，two-pointer算法，（有的叫滑动窗口算法），是一种应用比较广泛且重要的枚举算法，中间有一点贪心的味道存在。
基本特点：两个指针同时在一个一维数组上移动寻找一个符合题意的区间（或者看做两个数，起点和终点）
题目特点鲜明，可以解决一些贪心枚举问题与一些最值区间问题
为什么要学双指针算法：因为双指针算法有比暴力更加优越之处，那就是双指针算法的指针是不会回退的，所以效率更加高效
首先举一个简单的例子：
题目描述：
给定一个升序序列，找到两个数，使它们的和为x。 (保证序列中只有一组符合条件的两个数)
题目分析：
这道题可以用本文所说的双指针算法来做。我们首先定义两个指针i,j，通过移动这两个指针，实现比暴力更加快速的枚举查找
那么，如何实现让i和j优雅地移动到我们想移动的位置呢？
因为这道题是给定了一个上升序列，所以我们先假设：i总是在j的左边（这样可以方便思考），就可以知道，如果在某个位置，i+j的值是大于我们所要寻找的x的，那么在不移动i的情况下，就需要让j往左边移动。从而使得i+j的值更加逼近x，知道我们再去向右不断移动i，知道找到符合条件的i与j。
题目代码（本人手写，仅供参考）
#include <bits/stdc++.h>
using namespace std;
#define maxn 10086
int a[maxn],n,x;//定义数组，个人喜欢使用宏定义，const更好
int main()
{
cin>>n>>x;
for (int i=1;i<=n;i++)
cin>>a[i];//读入
for (int i=1,j=n;i<=n;i++)//进行主体运算
{
while (j>0&&a[i]+a[j]>x)j--;//寻找当前符合条件最小的j，也就是移动j 的操作
if (a[i]+a[j]==x&&j>0)//如果符合条件
{
cout<<i<<" "<<j<<endl;
return 0;//结束程序
}
}
return 0;
} 其实，在初学双指针的时候，我常常会疑惑（可能现在也还会疑惑），为什么不是先移动i再去移动j，如果当j在本题中无脑向后退，会不会有什么问题？
仔细想想，我就是一纯nt玩意儿，首先，想不出有什么情况可以hack的，其次i又不是一定要在j的右边。
以上为一道双指针的简单例题，接下来看一下第二道例题
题目描述：
Link
闲话：为什么一个骑士砍恶龙的题目描述要贴上这么一张加拿大鹅羽绒服的图片
本题首先可以用其它方法做，但是我们必须选择双指针
但是恶龙头和骑士的直径与能力值看起来并没有什么顺序，不像上一道例题一样给定了一个升序序列，所以我们要人为地把这两个数组变成有固定顺序的两个数组，这样才可以进行双指针算法的实操。
双指针算法是优雅地让两个指针移动，不是在一堆没有顺序的数字中乱跳。
当我们排好序后，题目思路就非常显然了，如果骑士A与骑士B都可以斩杀恶龙C，但是骑士A比骑士B要价更低，那么在恶龙必定会被斩杀的情况下，选择骑士A显然更加划算，由于本题关于骑士所得报酬和其能力值相同的特殊性质，所以以上的推导是成立的。
之后就可以进行代码构造了。
代码实现：
#include <iostream>
#include <algorithm>
#include <cstdio>
#define maxn 20086
using namespace std;
long long n,m,a[maxn],b[maxn];
int main()
{
while (scanf("%d%d", &n, &m) == 2 && n&& m)
{
int num=1,ans=0;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=m;i++) cin>>b[i];
sort(a,a+n+1);
sort(b,b+m+1);
for (int i=1;i<=m;i++)
if (b[i]>=a[num])
{
num++;
ans+=b[i];
if (num>n) break;
}
if (num>n) cout<<ans<<endl;else
cout<<"Loowater is doomed!"<<endl;
}
return 0;
}以上就是关于双指针算法的内容。感谢各位耐心听我胡言乱语。