在我看来，双指针的核心在于决策单调，因为单调性的存在，可以减小解空间，从而降低时间复杂度。

这里选了 cf 上一些思想比较典型的题目记录一下方便以后回顾。

个人认为难度比较低，但思想典型。

例题 1：

传送门：
https://codeforces.com/contest/1555/problem/E

让你选择若干条线段使得 $[1, m]$ 连通，求合法决策的最小极差。

分析

我们考虑将线段的权值作为关键字排序，那么注意到决策选取相邻的线段一定会得到答案。

因此我们可以考虑使用双指针，从小到大枚举 $l$ 指针，然后对于每个 $l$ 指针，我们找到最靠左合法的 $r$ 指针（所谓合法就是选取 $[l, r]$ 的 $r-l+1$ 条线段后 $[1,m]$ 是连通的）。

判断连通以及维护指针移动原区间对应的变化可以用线段树维护。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b

#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))

#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f

using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=3e5+5, M=1e6+5;

struct Seg{
    int l, r, w;
    bool operator < (const Seg &o)const{
        return w<o.w;
    }
}a[N];

struct Tree{
    int l, r; 
    int v, add;

    #define ls(u) u<<1
    #define rs(u) u<<1|1
}tr[M<<2];

int n, m;

void pushup(int u){
    tr[u].v=min(tr[ls(u)].v, tr[rs(u)].v);
}

void pushdown(int u){
    if(tr[u].add){
        auto &L=tr[ls(u)], &R=tr[rs(u)], &rt=tr[u];
        L.v+=rt.add, L.add+=rt.add;
        R.v+=rt.add, R.add+=rt.add;
        rt.add=0;
    }
}

void build(int u, int l, int r){
    tr[u]={l, r};
    if(l==r) return;
    int mid=l+r>>1;
    build(ls(u), l, mid), build(rs(u), mid+1, r);
}

void modify(int u, int l, int r, int k){
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].v+=k, tr[u].add+=k, void();
    int mid=tr[u].l+tr[u].r>>1;
    pushdown(u);
    if(l<=mid) modify(ls(u), l, r, k);
    if(r>mid) modify(rs(u), l, r, k);
    pushup(u);
}

int main(){
    read(n), read(m);
    rep(i,1,n){
        int l, r, w; read(l), read(r), read(w); r--;
        a[i]={l, r, w};
    }   

    sort(a+1, a+1+n);
    build(1, 1, m-1);

    int res=INF;
    for(int l=1, r=0; l<=n; l++){
        while(!tr[1].v){
            if(++r>n) break;
            modify(1, a[r].l, a[r].r, 1);
        }   
        if(r>n) break;
        res=min(res, a[r].w-a[l].w);
        modify(1, a[l].l, a[l].r, -1);
    }
    cout<<res<<endl;

    return 0;
}

例题 2：

传送门：
https://codeforces.com/contest/1539/problem/D

$n$ 种价格为 $2$ 的商品有属性 $a, b$，$a$ 是个数，$b$ 是当总共买够 $b$ 个商品（不限于本商品）时可以以价格 $1$ 购入（打对折）。求最少花多少钱买下所有商品。

分析

模拟 + 双指针

假设没有打折这个操作，那么所有商品价格都是 $2$，怎么决策都一样。

而我们是可以享受打折的，所以目标是最大化打折的商品数。

将所有种类的商品以 $b$ 为关键字升序排序。

当 $b$ 小的商品现在无法享受折扣时，我们可以去买 $b$ 大的商品。
而当现在购买的商品数足够让 $b$ 小的商品打折时，我们一定选择购买 $b$ 小的商品。

于是我们的决策一定是从两边到中间这样的，符合双指针的特征。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b

#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))

#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f

using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

#define int ll

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1e5+5;

struct Node{
    int a, b; 
    bool operator < (const Node &o)const{
        return b<o.b;
    }
}e[N];
int n;

signed main(){
    read(n);
    rep(i,1,n){
        int a, b; read(a), read(b);
        e[i]={a, b};
    }   

    sort(e+1, e+1+n);

    ll res=0;
    for(int l=1, r=n, cur=0; l<=r; ){
        while(cur<e[l].b && l<=r){
            while(cur+e[r].a<e[l].b && l<=r) res+=e[r].a*2, cur+=e[r].a, r--;
            if(l>r) break;
            e[r].a-=e[l].b-cur, res+=2*(e[l].b-cur), cur+=e[l].b-cur;
        }
        if(l>r) break;
        while(cur>=e[l].b && l<=r){
            cur+=e[l].a, res+=e[l].a;
            l++;
        }
    }
    cout<<res<<endl;

    return 0;
}

例题 3：

传送门：
https://codeforces.com/contest/701/problem/C

给你一个字符串，找到最短的子段，满足字符串出现的所有字符在子段中出现。

分析

这道题很经典。

可以发现如果子段 $[l, r]$ 是满足的，那么 $[l, r+d]$ 也一定满足，所以这是满足决策单调的。

所以我们可以枚举 $l$ 指针，然后从上次决策的 $r$ 的位置继续枚举，复杂度为 $O(n)$。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b

#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))

#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f

using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1e5+5, M=200;
char s[N];
bool vis[M];
int cnt[M];

bool check(){
    rep(i,0,M-1) if(vis[i] && !cnt[i]) return false;
    return true;
}

int main(){
    int n; cin>>n;
    cin>>s+1;

    rep(i,1,n) vis[s[i]-'A']=true;

    cnt[s[1]-'A']++;
    int j=1, res=INF;
    rep(i,1,n){
        while(!check() && j<n){
            j++;
            cnt[s[j]-'A']++;
        }
        if(!check() && j==n) break;
        res=min(res, j-i+1);
        cnt[s[i]-'A']--;
    }
    cout<<res<<endl;
    return 0;
}

例题 4：

传送门：
https://codeforces.com/contest/1469/problem/C

题意可以看洛谷的：
https://www.luogu.com.cn/problem/CF1469C

分析

注意到当前篱笆的决策范围只和上一个有关，所以我们可以维护一个区间 $[l, r]$ 表示可以决策的范围，模拟一下就好了。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=2e5+5;

int h[N];

int main(){
    int T; cin>>T;
    while(T--){
        int n, k; read(n), read(k);
        rep(i,1,n) read(h[i]);

        int l=h[1], r=h[1];
        bool ok=true;
        rep(i,2,n){
            l=max(h[i], l-k+1), r=min(r+k-1, h[i]+k-1);
            // debug(l), debug(r);
            if(l>r){
                ok=false;
                break;
            }
        }
        if(l!=h[n]) ok=false;

        puts(ok? "YES": "NO");
    }   
    return 0;
}

例题 5：

传送门：
https://codeforces.com/gym/101775/problem/J

题意：
给你一个序列，每次操作你可以将长度大于等于 $3$ 且小于等于 $5$ 的区间同时 $-1$，问是否能在一定次数的操作后使序列全部为 $0$。

分析：
其实题目所说的操作可以直接转化为：每次操作你可以将长度大于等于 $3$ 的区间 $-1$。

使用差分的思想，我们只需要使差分序列的 $l$ 点的值 $-1$，$r+1$ 的点值 $+1$。接下来对于当前差分序列所在负数，我们都从差分序列找正数直到当前负数被抵消为 $0$，依次下去即可。

细节见代码。

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb push_back
#define eb emplace_back
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b

#define all(x) (x).begin(), (x).end()
#define SUM(a) accumulate(all(a), 0LL)
#define MIN(a) (*min_element(all(a)))
#define MAX(a) (*max_element(all(a)))
#define lb(a, x) distance(begin(a), lower_bound(all(a), (x)))
#define ub(a, x) distance(begin(a), upper_bound(all(a), (x)))

#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f

using pii = pair<int, int>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vpii = vector<pii>;
using ll = long long;
using ull = unsigned long long;

#define int ll

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=2e5+5;

int n;
int w[N], d[N];

signed main(){
    int T; cin>>T;
    int C=0;
    while(T--){
        printf("Case #%d: ", ++C);

        read(n);
        rep(i,1,n) read(w[i]);
        w[n+1]=0;
        rep(i,1,n+1) d[i]=w[i]-w[i-1];
        // rep(i,1,n+1) cerr<<d[i]<<' ';
        // cerr<<endl;

        bool ok=true;
        int p=4;
        rep(i,1,n+1){
            p=max(p, i+3);
            // debug(p);
            if(d[i]<0){
                ok=false;
                break;
            }
            if(!d[i]) continue;
            while(d[i]>0 && p<=n+1){
                while(d[p]>=0 && p<=n+1) p++;
                if(p==n+2){
                    ok=false;
                    break;
                }

                if(d[i]+d[p]>0) d[i]+=d[p], d[p]=0, p++;
                else d[p]+=d[i], d[i]=0;
            }
            if(d[i]>0){
                ok=false;
                break;
            }
        }

        puts(ok? "Yes": "No");
    }
    return 0;
}