尺取法
尺取法核心思路
尺取法其实也是一种模拟，是解决寻找区间和问题的一种方法。
假如有这么一个问题：给你一些数，请在这些数中找到一个区间，使得区间里每一个元素的和大于或等于给定的某个值。
不会尺取法的话，肯定就会开双重循环，枚举区间起点和终点，然后每一次都求一次和，再和给定的数作比较。
尺取法与它的思路类似，都是寻找一个区间的起点和终点。做法是:
用两个指针，最初都指向，这一组数中的第一个，然后如果这个区间的元素之和小于给定的数，就把右指针向右移，直到区间和大于等于给定的值为止。之后把左指针向右移，直到区间和等于给定的值为止，保存方案，继续操作。
假如左指针指向这些数的第一个，并且右指针指向这组数的最后一个，这种情况下的子区间元素之和仍然小于给定的数的话，那么就输出-1，表示不可能。
那么怎么求区间和呢？
当然，for一遍是可以的，但是太浪费时间了。我们可以引入一个累加器，初始值等于这组数中的第一个元素（因为最开始左指针和右指针都指向它），当右指针向右移时，累加器每次就加上右指针指向的元素的值。当左指针向右移时，累加器每次就减去左指针指向的值。
怎么实现呢？
实现
这里有道模板题
下面附上代码（不是我写的）
#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总指向当前满足要求区间的下一个 注意此处R可能>N
{
sum+=a[R];//累加器加上右指针指向的元素
++R;//右指针向右移
++lsub;
}
while(sum>=S)//L总指向当前区间的最左边 左闭右开
{
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;
}
尺取法嘛。。应该很好懂，就是一种模拟的策略。
在各大竞赛都会用到（还有90天了）
