尺取法two pointers

目的：对给定的一个序列，在序列中寻找包含全部需求的、长度最小的一段子序列。一般用来解决具有单调性的区间问题。

时间复杂度：O(n)

https://blog.csdn.net/lxt_lucia/article/details/81091597

自用模板：

poj3061，给定一个序列，使得其和大于或等于S，求最短的子序列长度。

#include<stdio.h>

#include<iostream>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn=1e5+;

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,s,a[maxn],st=,en=,ans=INF;

        long long sum=;

        scanf("%d%d",&n,&s);

        for(int i=;i<n;i++)scanf("%d",&a[i]);

        while()

        {

            while(en<n&&sum<s)sum+=a[en++];

            if(sum<s)break;  //如果右端点移动到区间末尾其和还不大于等于S，结束区间的枚举

            ans=min(ans,en-st);

            sum-=a[st++];

        }

        if(ans==INF)ans=;

        printf("%d\n",ans);

    }

    return ;

}

poj3320，一本书有P页，每一页都一个知识点，求去最少的连续页数覆盖所有的知识点，使用map来查询次数。

#include<stdio.h>

#include<iostream>

#include<map>

#include<set>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn=1e6+;

map<int,int> mp;

set<int> s;

int main()

{

    int n,a[maxn],st=,en=,ans=INF,num,sum=;

    scanf("%d",&n);

    for(int i=;i<n;i++)scanf("%d",&a[i]),s.insert(a[i]);

    num=s.size();

    while()

    {

        while(en<n&&sum<num)

        {

            if(mp[a[en]]==)sum++;

            mp[a[en]]++;

            en++;

        }

        if(sum<num)break;

        ans=min(ans,en-st);

        mp[a[st]]--;

        if(mp[a[st]]==)sum--;

        st++;

    }

    if(ans==INF)ans=;

    printf("%d\n",ans);

    return ;

}

poj2739，找到某一个区间使得连续和等于某一给定值k。

#include<stdio.h>

#include<iostream>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn=1e5+;

bool prime[maxn];

int p[maxn],tot;

void init()

{

    for(int i=;i<;i++)prime[i]=true;

    for(int i=;i<;i++)

    {

        if(prime[i])p[tot++]=i;

        for(int j=;j<tot&&i*p[j]<;j++)

        {

            prime[i*p[j]]=false;

            if(i%p[j]==)break;

        }

    }

}

int main()

{

    init();

    int n;

    while(scanf("%d",&n),n!=)

    {

        int st=,en=,ans=,sum=;

        while()

        {

            while(en<n&&sum<n)sum+=p[en++];

            if(sum==n)ans++;

            if(st==en)break;

            sum-=p[st++];

        }

        printf("%d\n",ans);

    }

    return ;

}

poj2100，找到某一个区间使得区间内的数的平方和等于某一给定值k。不加1LL的比较超时了(什么鬼哦)，代码二的样式我jio的不错。

#include<stdio.h>

#include<iostream>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn=1e5+;

struct node

{

    int l,r;

}p[maxn];

int main()

{

    long long n;

    scanf("%lld",&n);

    int st=,en=,ans=,k=;

    long long sum=;

    while()

    {

        while(1ll*en*en<=n&&sum<n)sum+=1ll*en*en,en++;

        if(sum==n)ans++,p[k].l=st,p[k++].r=en-;

        if(sum<n)break;

        sum-=1ll*st*st,st++;

    }

    printf("%d\n",ans);

    for(int i=;i<k;i++)

    {

        printf("%d ",p[i].r-p[i].l+);

        for(int j=p[i].l;j<p[i].r;j++)

        printf("%d ",j);

        printf("%d\n",p[i].r);

    }

    return ;

}

#include<stdio.h>

#include<iostream>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn=1e5+;

struct node

{

    int l,r;

}p[maxn];

int main()

{

    long long n,sum=,st=,en=;

    int ans=,k=;

    scanf("%lld",&n);

    while()

    {

        if(sum==n)ans++,p[k].l=st,p[k++].r=en-;

        if(sum>=n)sum-=1ll*st*st,st++;

        else

        {

            if(en*en<=n)sum+=1ll*en*en,en++;

            else break;

        }

    }

    printf("%d\n",ans);

    for(int i=;i<k;i++)

    {

        printf("%lld ",p[i].r-p[i].l+);

        for(long long j=p[i].l;j<p[i].r;j++)

        printf("%lld ",j);

        printf("%lld\n",p[i].r);

    }

    return ;

}

uva 11572，求没有重复数字的最长区间。

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

const int maxn=1e6+;

int a[maxn];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        map<int,int> mp;

        int n,ans=,st=,en=,sum=;

        scanf("%d",&n);

        for(int i=;i<n;i++)scanf("%d",&a[i]);

        while()

        {

            while(en<n)

            {

                if(mp[a[en]]==)sum++,mp[a[en]]++,en++;

                else break;

            }

            ans=max(ans,en-st);

            if(en==n)break;

            if(mp[a[st]]==)mp[a[st]]--;

            sum--;

            st++;

        }

        printf("%d\n",ans);

    }

    return ;

}

atcoder 4142，求满足区间内a_l+a_l+1+a_l+2+...+a_r==a_l^a_l+1^a_l+2^...^a_r的区间个数

异或性质：a^b<=a+b，当且仅当a&b等于0时取等

#include<stdio.h>

#include<iostream>

using namespace std;

const int maxn=2e5+;

long long a[maxn];

int main()

{

    int n,en=,st=;

    long long sum=,ans=;

    scanf("%d",&n);

    for(int i=;i<n;i++)scanf("%lld",&a[i]);

    while()

    {

        while(en<n)

        {

            if((sum&a[en])==)sum+=a[en++],ans+=en-st;

            else break;

        }

        if(en==n)break;

        sum-=a[st++];

    }

    printf("%lld\n",ans);

    return ;

}

洛谷 p1102 a-b数对，这题直接map一下就好了，强行尺取要先来个sort排序，[枚举每个B+查询对应A]复杂度为O(n)，sort完二分也可，尺取的优化在于B+C已经比最大的数大了，就break。

(*╹▽╹*)这题没有代码

poj2566，求一段子序列之和的绝对值最接近所给出的t，不能直接用尺取所以前缀+sort一哈，细节略多，试了很久。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#define INF 0x3f3f3f3f

using namespace std;

const int maxn=1e5+;

int n,en,st,k,a[maxn],l,r,sum,ans,res,s;

pair<int,int> pre[maxn];

int main()

{

    while(scanf("%d%d",&n,&k)&&n!=&&k!=)

    {

        pre[]=make_pair(,);

        for(int i=;i<=n;i++)scanf("%d",&a[i]),pre[i].first=pre[i-].first+a[i],pre[i].second=i;

        sort(pre,pre++n);

        while(k--)

        {

            en=,st=,ans=INF,res=INF;  //en=0会wa

            scanf("%d",&s);

            while(en<=n)

            {

                int tmp=pre[en].first-pre[st].first;

                if(abs(tmp-s)<=res)

                {

                    res=abs(tmp-s);

                    ans=abs(tmp);

                    l=pre[st].second,r=pre[en].second;

                }

                if(tmp<s)en++;

                else if(tmp>s)st++;

                else break;

                if(en==st)en++;  //这句没有会wa

            }

            if(l>r)swap(l,r);

            printf("%d %d %d\n",ans,l+,r);  //前缀l和r之间包括了数l+1到r，所以刚开始要加pre[0]

        }

    }

    return ;

}

...over

巴特西

尺取法two pointers

最新文章

热门文章