尺取法

尺取法核心思路

尺取法其實(shí)也是一種模擬，是解決尋找區(qū)間和問(wèn)題的一種方法。

假如有這么一個(gè)問(wèn)題：給你一些數(shù)，請(qǐng)?jiān)谶@些數(shù)中找到一個(gè)區(qū)間，使得區(qū)間里每一個(gè)元素的和大于或等于給定的某個(gè)值。

不會(huì)尺取法的話，肯定就會(huì)開雙重循環(huán)，枚舉區(qū)間起點(diǎn)和終點(diǎn)，然后每一次都求一次和，再和給定的數(shù)作比較。

尺取法與它的思路類似，都是尋找一個(gè)區(qū)間的起點(diǎn)和終點(diǎn)。做法是:

用兩個(gè)指針，最初都指向，這一組數(shù)中的第一個(gè)，然后如果這個(gè)區(qū)間的元素之和小于給定的數(shù)，就把右指針向右移，直到區(qū)間和大于等于給定的值為止。之后把左指針向右移，直到區(qū)間和等于給定的值為止，保存方案，繼續(xù)操作。

假如左指針指向這些數(shù)的第一個(gè)，并且右指針指向這組數(shù)的最后一個(gè)，這種情況下的子區(qū)間元素之和仍然小于給定的數(shù)的話，那么就輸出-1，表示不可能。

那么怎么求區(qū)間和呢？

當(dāng)然，for一遍是可以的，但是太浪費(fèi)時(shí)間了。我們可以引入一個(gè)累加器，初始值等于這組數(shù)中的第一個(gè)元素（因?yàn)樽铋_始左指針和右指針都指向它），當(dāng)右指針向右移時(shí)，累加器每次就加上右指針指向的元素的值。當(dāng)左指針向右移時(shí)，累加器每次就減去左指針指向的值。

怎么實(shí)現(xiàn)呢？

實(shí)現(xiàn)

這里有道模板題

poj3061

下面附上代碼（不是我寫的）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int a[100000+33];
int ans,S,N;

void solve()
{
    ans=100000+44; 
    int L=1,R=1,sum=0,lsub=0;
    while(R<=N)
    {
        while(sum<S&&R<=N)//R總指向當(dāng)前滿足要求區(qū)間的下一個(gè) 注意此處R可能>N 
        {
            sum+=a[R];//累加器加上右指針指向的元素
            ++R;//右指針向右移
            ++lsub;
        }
        while(sum>=S)//L總指向當(dāng)前區(qū)間的最左邊  左閉右開 
        {
            sum-=a[L];//累加器減去左指針指向的元素的值
            ++L;//左指針右移
            --lsub;
        }
        ans=min(ans,lsub+1);
    }
}

int main()
{
    int T,i,sum;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&N,&S);
        sum=0; bool flag=false;
        for(i=1;i<=N;++i) 
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            if(sum>=S&&!flag) flag=true;    
        }
        if(!flag)
        {
            printf("0\n"); continue;
        }
        solve();
        printf("%d\n",ans);
    }
    return 0;
}

尺取法嘛。。應(yīng)該很好懂，就是一種模擬的策略。

在各大競(jìng)賽都會(huì)用到（還有90天了）