尺取法入门

  给出长度为n的数列以及整数s,求出总和不小于s的连续子序列长度的最小值,如果不存在,输出0。

尺取法原理; 
假设a1+a2+…+a4>s 
此时说明a2+a3< a1+a2+a3< s 
那么如果我们想继续向前找,a2+a3+…+at>s。t一定是大于等于4 
这说明,如果依次寻找,不用考虑中间点的影响,决定子序列是否满足条件的是他的两个端点,因此我们可以通过对两个端点的调控,达到遍历找出答案的目的 
1.表示方法: 
我们用数组存数据,sum存子序列和,然后用i表示左端点,t表示右端点 
2.调控方法: 
右端点向右移动,那就是t++,移动之后,sum+a[t] 
左端点向右移动,就是i++,移动之后,sum-a[i]

3.移动条件: 
sum< s,右端点移动,左端点不动 
sum>s,左端点移动,右端点不动 

板子:

void solve(){
    int res=n+1;
    int i=0,t=0,sum=0;
    for(;;){
        while(t<n&&sum<s){
            sum+=a[t++];
        }
        if(sum<s) break;
        res=min(res,t-i);
        sum-=a[i++];
    }
    if(res>n){
        res=0;
    }
    printf("%d
",res);
}
原文地址:https://www.cnblogs.com/eason9906/p/11754920.html