poj3061 Subsequence&&poj3320 Jessica's Reading Problem(尺取法)

这两道题都是用的尺取法。尺取法是《挑战程序设计竞赛》里讲的一种常用技巧。

就是O（n）的扫一遍数组，扫完了答案也就出来了，这过程中要求问题具有这样的性质：头指针向前走（s++）以后，尾指针（t）要么不动要么也往前走。满足这种特点的就可以考虑尺取法。

poj3061 比较简单，也可以用二分做，时间复杂度O（n*logn）。用尺取法可以O（n）解决。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

#include<cctype>

#include<sstream>

using namespace std;

#define INF 1000000000

#define eps 1e-8

#define pii pair<int,int>

#define LL long long int

int T,N,S,a[];

int main()

{

    //freopen("in7.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&N,&S);

        int ans=INF;

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

        {

            scanf("%d",&a[i]);

        }

        int s=,t=,sum=;

        while()

        {

            while(t<N&&sum<S)

            {

                sum+=a[t];

                t++;

            }

            if(sum<S) break;

            ans=min(ans,t-s);

            //注意这里的距离不是(t-s+1),因为我前一个while中最后t++了，所以

            //现在是s到t的左闭右开区间

            sum-=a[s];

            s++;

        }

        if(ans<INF)

            cout<<ans<<endl;

        else

            cout<<''<<endl;

    }

    //fclose(stdin);

    //fclose(stdout);

    return ;

}

poj3320 对数据用set和map来处理显得很方便，核心部分也是尺取法。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

#include<cctype>

#include<sstream>

using namespace std;

#define INF 1000000000

#define eps 1e-8

#define pii pair<int,int>

#define LL long long int

int P,a[];

set<int>st;

map<int,int>mp;

int main()

{

   // freopen("in8.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    scanf("%d",&P);

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

    {

        scanf("%d",&a[i]);

        st.insert(a[i]);

    }

    int tol=st.size();

    int s=,t=;

    int ans=INF;

    for(;;)

    {

        while(t<P&&mp.size()<tol)

        {

            if(mp.count(a[t])) mp[a[t++]]++;

            /*在map里用count函数，有返回1，没有就返回0*/

            else mp[a[t++]]=;

        }

        if(mp.size()<tol) break;

        ans=min(ans,t-s);

        mp[a[s]]--;

        if(mp[a[s]]==) mp.erase(a[s]);

        s++;

    }

    cout<<ans<<endl;

    //fclose(stdin);

    //fclose(stdout);

    return ;

}