尺取法
尺取法核心思路
尺取法其實也是一種模擬陵吸，是解決尋找區(qū)間和問題的一種方法蜒蕾。
假如有這么一個問題：給你一些數(shù)薇芝，請在這些數(shù)中找到一個區(qū)間茫死，使得區(qū)間里每一個元素的和大于或等于給定的某個值路翻。
不會尺取法的話狈癞，肯定就會開雙重循環(huán)，枚舉區(qū)間起點和終點茂契，然后每一次都求一次和蝶桶，再和給定的數(shù)作比較。
尺取法與它的思路類似掉冶，都是尋找一個區(qū)間的起點和終點真竖。做法是:
用兩個指針，最初都指向厌小，這一組數(shù)中的第一個恢共，然后如果這個區(qū)間的元素之和小于給定的數(shù)，就把右指針向右移璧亚，直到區(qū)間和大于等于給定的值為止讨韭。之后把左指針向右移，直到區(qū)間和等于給定的值為止癣蟋，保存方案透硝，繼續(xù)操作。
假如左指針指向這些數(shù)的第一個疯搅，并且右指針指向這組數(shù)的最后一個濒生，這種情況下的子區(qū)間元素之和仍然小于給定的數(shù)的話，那么就輸出-1秉撇，表示不可能甜攀。
那么怎么求區(qū)間和呢？
當然琐馆，for一遍是可以的规阀，但是太浪費時間了。我們可以引入一個累加器瘦麸，初始值等于這組數(shù)中的第一個元素（因為最開始左指針和右指針都指向它）谁撼，當右指針向右移時，累加器每次就加上右指針指向的元素的值。當左指針向右移時厉碟，累加器每次就減去左指針指向的值喊巍。
怎么實現(xiàn)呢？
實現(xiàn)
這里有道模板題
下面附上代碼（不是我寫的）
#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總指向當前滿足要求區(qū)間的下一個 注意此處R可能>N
{
sum+=a[R];//累加器加上右指針指向的元素
++R;//右指針向右移
++lsub;
}
while(sum>=S)//L總指向當前區(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)該很好懂，就是一種模擬的策略款咖。
在各大競賽都會用到（還有90天了）
