【思想】双指针

更新于 分类于 ， 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

双指针，又称尺取法，常解决与单调性有关的区间问题

根本不知道这玩意是种算法系列…

概念

其实就是维护区间的两端l,rl,r ，在满足条件的情况下让rr 不断向右移动直到不符合条件，再让ll 移动。

显然这种方法的特性是当[l,r][l,r] 满足条件时，∀i∈[l,r]\forall i\in [l,r] ，[l,i][l,i] 都满足条件，因此可以解决一些满足特定条件的计数问题。

所谓“单调性”即为，当ll 开始移动时，rr 不可能向左移动，即若[l,r][l,r] 满足条件但[l,r+1][l,r+1] 不满足条件（非边界条件），那么∀i∈[l,r]\forall i\in [l,r] ，[l+1,i][l+1,i] 必不可能满足条件。

佬说，因为单调性的存在，能用双指针解决的问题一般可以找到单调性，并用二分解决。

复健时候的题目会放上来，并不是入门的好材料，咕咕咕

题目

CF1611F

Problem - F - Codeforces

题意

给定数组aa ，长为nn ，给定常数SS ，寻找最长的区间[x,y][x,y] 使得∀i∈[x,y],∑j=xiaj≥−S\forall i\in [x,y],\sum_{j=x}^i a_j\geq -S ，即区间内的所有前缀和都≥−S\geq -S

分析

肯定需要先处理出前缀和数组dd ，问题变成了找最长区间[x,y][x,y] 使得∀i∈[x,y],d[i]−d[x−1]≥−S\forall i\in [x,y],d[i]-d[x-1]\geq -S

因为题目规模，估计复杂度最多在O(nlog⁡n)O(n\log n) （不纠结log的指数），考虑在枚举一个左端点时如何在log⁡n\log n 的时间内找到最远的右端点

为了找更长的区间，固定左端点，如果[l,r][l,r] 满足题意，显然更小的区间都满足题意（左端点仍是ll ）；若此时[l,r+1][l,r+1] 不满足题意，为了更长没有必要把rr 向左移动，因此这里其实已经是双指针了。

注意到d[x−1]−Sd[x-1]-S 是个定值，问题还可改写为找最长区间[x,y][x,y] 使得min⁡{d[i]∣i∈[x,y]}≥d[x−1]−S\min \{d[i]|i\in[x,y]\}\geq d[x-1]-S ，区间最值…RMQ，到此问题解决了，最终复杂度ST表预处理O(nlog⁡n)O(n\log n) ，双指针复杂度O(n)O(n) 。

当然也可以二分找右端点，不如双指针简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
ll st[N][20];
int n,s;
void init()
{
    for(int j=1;j<20;j++)
        for(int i=1;i<=n&&i+(1<<(j-1))<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
ll query(int x,int y)
{
    int k=log(y-x+1);
    return min(st[x][k],st[y-(1<<k)+1][k]);
}
void solve()
{
    cin>>n>>s;
    for(int i=1,tmp;i<=n;i++)
    {
        cin>>tmp;
        st[i][0]=st[i-1][0]+tmp;
    }
    init();
    int l=1,r=1,ans=-1,x,y;
    while(l<=n&&r<=n)
    {
        if(l>r)
            r=l;
        if(query(l,r)<st[l-1][0]-s)
            l++;
        else
        {
            if(r-l+1>ans)
                x=l,y=r,ans=r-l+1;
            r++;
        }
    }
    if(~ans)
        cout<<x<<' '<<y<<'\n';
    else
        cout<<"-1\n";
}