Skip to content

尺取法 two-pointers

用途

用来处理一些具有单调性的区间问题。

主要流程就是枚举一个左端点\(l\)，求出合法序列对应的右端点\(r\).

单调性可能指对于一个左端点\(l\)，一个合法的序列为\([l,r]\)，那么\([l,r-1]\)和\([l+1,r]\)一定不合法,等等。这分别保证了右端点不会左移和左端点右移不会漏解。

尺取法的复杂度一般为\(O(n)\)，因为单调性保证向右顺序枚举\(l\)时，\(r\)不会向左移动。

"尺取法就是在对于枚举每一个 l 的时候,另一个坐标 r 维护的答案也是单调的时候可以使用,能够均摊枚举的时间从而把时间复杂度降到 O(n) . "

例题

P1638

枚举\(l\)并求出每个合法的右端点\(r\),并统计最小值即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int n,m,el,er;
int a[N],cnt[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    int l=1,r=0,now=0,ans=n+1;
    for(;l<=n;){
        while(now<m && r<n)now+=!cnt[a[++r]]++?1:0;
        if(now<m)break;
        if(ans>r-l+1)el=l,er=r,ans=r-l+1;
        now-=!--cnt[a[l++]]?1:0;
    }
    printf("%d %d",el,er);
    return 0;
}

UVA11572

如果\([l,r]\)不合法，则\([l,r+1]\)一定不合法，这就保证单调性：如果\([l,r]\)不合法，就不用枚举后面的\(r\)了，直接右移\(l\).

  • 所有的尺取都是只要满足/不满足某一条件就可以右移\(l\)并且\(r\)不会左移。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int T,n;
int a[N],cnt[N],b[N];
bool cmp(int a,int b){
    return a<b;
}
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1,cmp);
    int tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
}
int main(){
    scanf("%d",&T);
    while(T--){
        init();
        int l=1,r=0,ans=0;
        memset(cnt,0,sizeof cnt);
        for(;l<=n;){
            while(r<n){
                if(cnt[a[r+1]])break;
                else cnt[a[++r]]++;
            }
            ans=max(ans,r-l+1);
            --cnt[a[l++]];
        }
        printf("%d\n",ans);
    }
    return 0;
}

AT4142

这题也满足单调性。

设\(a_l+...+a_r=sum_a,a_lxor...xora_r=sum_b\),则满足\(sum_a\geq sum_b\),所以如果\(sum_a>sum_b\)，后面的\(r\)都不用枚举了。

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=2e5+10;
int n;
int a[N];
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    int l=1,r=0,sum=0,nowa=0,nowb=0;
    for(;l<=n;){
        while(r<n){
            if((nowa+a[r+1])>(nowb^a[r+1]))break;
            ++r;
            nowa+=a[r];
            nowb^=a[r];
        }
        sum+=r-l+1;
        nowa-=a[l];
        nowb^=a[l];
        l++;
    }
    printf("%lld",sum);
    return 0;
}
也可以二分，对于每个\(l\)二分出最后满足\(sum_a=sum_b\)的右端点\(r\),时间复杂度\(O(nlogn)\)
  • 结论：二分不一定要二分答案，也可以对左端点每次都二分右端点。

CF47E

~~属于有思路但写不对代码的题了~~

一开始看题就注意到\(0<\alpha<\frac\pi4\),这意味着抛物线的高度和距离时单调递增的。

\[x=\frac{v^2\sin2\alpha}{g}\\y=\frac{v\sin\alpha}{g}\]

这样就可以用尺取法了,因为如果炮弹打在墙上，那么比他角度小的炮弹也一定打在墙上。

对于所有炮弹的角度排个序，对墙的横坐标也排个序。

如果计算出\(y\leq 0\)说明打在地上，直接计算地上横坐标。

如果计算\(0<y\leq s[l].y\),说明打在墙上。

最后直接输出\(ans[i]\)即可。

CF430B

  • 这题提醒我们双指针不一定要像"尺"一样从左到右扫区间，还可以从中间向两边扩散。

注意第一次的计数\(cnt-1\).

#include<iostream>
#include<cstdio>
using namespace std;
const int N=220;
int n,k,x,maxn;
int a[N];
int main(){
    scanf("%d%d%d",&n,&k,&x);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=0;i<=n;++i){
        int l=i,r=i+1,now=x,cnt=1,ans=0,flag=-1;
        for(int time=1;;time++){
            while(l>=1 && now==a[l])--l,++cnt;
            while(r<=n && now==a[r])++r,++cnt;
            if(cnt<=2)break;
            ans+=cnt+flag;
            if(a[l]!=a[r] || l==0 && r==n+1)break;
            now=a[l];
            cnt=0;
            flag=0;
        }
        maxn=max(maxn,ans);
    }
    printf("%d",maxn);
    return 0;
} 
/*
50 2 1
1 1 2 2 1 2 1 1 2 2 1 2 1 2 1 1 2 2 1 2 1 2 2 1 2 1 2 1 2 2 1 1 2 2 1 1 2 2 1 2 1 1 2 1 1 2 2 1 1 2
*/

CF939E

贪心尺取法。

有两条重要性质。

1) 对于一个加入的新数一定要选。

$$ 原式 ans=Max-\frac{sum}{n}\

考虑用新的最大替换掉原来的最大，设新的最大比原来最大大 \Delta(x)\ ans=\frac{(Max+\Delta(x))\times n-(sum+\Delta(x))}{n}\

因为 n\geq 1，ans一定变大（优秀） $$ 2) 对于集合 s 剩下的数，一定是选前面几个小的数，并且选的数的个数是单调不减的。

可以意会一下证明，一定是选比当前集合平均数小的数加进来，使平均数更小，答案才会变得更大。 $$ 原式 ans=Max-\frac{sum}{n}\

考虑新加一个数 \Delta(x)\ 新的式子 ans=Max-\frac{sum+\Delta(x)}{n+1}\

若新式减去原式>0，则新式更优秀\ 新式减原式得\ -\frac{sum+\Delta(x)}{n+1}+\frac{sum}{n}\

等于\ \frac{sum-n\times \Delta(x)}{n\times(n+1)}>0\

得出更优秀条件为：sum-n\times \Delta(x)>0，即 \Delta(x) <\frac{sum}{n}\ $$

证毕，可以用尺取法。

#include<iostream>
#include<cstdio>
#include<cstring>
#define db double
#define int long long 
using namespace std;
const int N=5e5+10;
int n,cnt,tot;
int vis[N],q[N];
db res[N],a[N],sum[N];
int read1(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')f=-1;
        ch=getchar();
    }   
    while(ch<='9' && ch>='0'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void work(){
    int l=1,r=0;
    db ans=-1.0;
    for(int i=1;i<=cnt;++i)sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=cnt;++i){
        if(!vis[i])continue;
        ans=-1.0;
        while(l<=i){
            db tmp=(double)(a[i]-(double)(sum[l]+a[i])/(l+1));
            if(tmp>ans)ans=tmp,++l;
            else{
                --l;
                break;  
            }
        }
        if(l==i+1)--l;
        res[i]=ans;
    }
    for(int i=1;i<=tot;++i)printf("%.10lf\n",res[q[i]]);

}
signed main(){
    cnt=0,tot=0;
    n=read1();
    for(int i=1,op;i<=n;++i){
        op=read1();
        if(op==1){
            a[++cnt]=(double)read1();
        }else{
            vis[cnt]=1;
            q[++tot]=cnt;
        }
    }
    work();
    return 0;   
}