[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法


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 15
5 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)。

上述流程反复地推进区间的开头和末尾,来求取满足条件的最小区间。

----------------------------------------------------------------------------------------------------------------------------------------------------------

[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法 View Code

 

>>>>>>>>> 同样也可以用用lower_bound:

   --------------------------------------------------------------------------------------------------------------------------------------------------------

   lower_bound(ForwardIterator first,ForwardIterator last, const Type &value,Compare comp );

 lower_bound()返回一个 iterator 它指向在[first,last)标记的有序序列中可以插入value,而不会破坏容器顺序的第一个位置,而这个位置标记了一个大于等于value 的值。

   例如,有如下序列:

   ia[]={12,15,17,19,20,22,23,26,29,35,40,51};
   用值21调用lower_bound(),返回一个指向22的iterator。用值22调用lower_bound(),也返回一个指向22的iterator。根据comp进行排序和比较。
 注意:::调用lower_bound之前必须确定序列为有序序列,否则调用出错。函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于    val的第一个元素位置。如果所有元素都小于val,则返回last的位置。
   --------------------------------------------------------------------------------------------------------------------------------------------------------
   所以这里我们可以这样处理:

   我们可以计算出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小的最小值的下标。

[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法 View Code

 

>>>>>>>>附加:折半查找法:

[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法 lower_bound版本一:
[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法 lower_bound版本二:
[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法 upper_bound版本一:
[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法 upper_bound版本二:
[ACM_其他] 总和不小于S的连续子序列的长度的最小值——尺缩法 折半查找:

 



本文转自beautifulzzzz博客园博客,原文链接:http://www.cnblogs.com/zjutlitao/p/3485545.html,如需转载请自行联系原作者

上一篇:thinkphp-条件判断-范围判断-notin


下一篇:《Nmap渗透测试指南》—第6章6.2节报文分段