Description:
给定长度为n的整数数列，A[0],A[1],A[2]….A[n-1]以及整数S，求出总和不小于S的连续子序列的长度的最小值。如果解不存在，则输出0。
Input:
输入数据有多组，每组数据第一行输入n,S, （10<n<10^5,S<10^8）第二行输入A[0],A[1],A[2]….A[n-1] ( 0<A[i]≤10000)，处理到文件结束。所有输入数据都在int范围之内。
Output:
每组数据输出结果占一行。
Sample Input:
10 155 1 3 5 10 7 4 9 2 8
Sample Output:
2 >>>>>>>>>这题有一个技巧，叫做尺缩法 -----------------------------------------------------------------------------------------------------------------------
（1） 设置两个指针s和t，一开始都指向数列第一个元素，此外sum=0,res=0；
（2） 只要sum<S，就将sum增加一个元素，t加1；
（3） 直到sum>=S，更新res=min(res,t-s)；
（4） 将sum减去一个元素，s加1，执行（2）。
上述流程反复地推进区间的开头和末尾，来求取满足条件的最小区间。
----------------------------------------------------------------------------------------------------------------------------------------------------------
View Code
>>>>>>>>> 同样也可以用用lower_bound:
--------------------------------------------------------------------------------------------------------------------------------------------------------
lower_bound(ForwardIterator first,ForwardIterator last, const Type &value,Compare comp );
lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个大于等于value 的值。
例如，有如下序列：
我们可以计算出sum(i)=a0+a1+...+ai。那么sum(t)-sum(s)=as+a(s+1)+...a(t-1)。这样我们可以实现先求出一个sum(n)。sum(n)-sum(i)=s。我们只需要去筛选sum(i)。这样可以用二分搜索的方法快速求出最小的长度。
int t=lower_bound(sum+i,sum+n,sum[i]+s)-sum;求出来的是从ai到at(i<=t<=n)和比s小的最小值的下标。
View Code
>>>>>>>>附加：折半查找法：
lower_bound版本一： lower_bound版本二： upper_bound版本一： upper_bound版本二： 折半查找：
本文转自beautifulzzzz博客园博客，原文链接：http://www.cnblogs.com/zjutlitao/p/3485545.html，如需转载请自行联系原作者