POJ 3061 Subsequence 二分或者尺取法

题目大意：

给定长度为n的整列整数a[0],a[1],……a[n-1]，以及整数S，求出总和不小于S的连续子序列的长度的最小值。

思路:

方法一：

首先求出各项的和sum[i]，这样可以在O(1)的时间内算出区间上的总和，这样，枚举每一个起点i，然后二分搜索出结果大于sum[i]+tot的最小下标。（tot是题目中的S）

总的时间为O(nlogn）

方法二：

设以a[s]开始的总和最初大于S时的连续子序列为a[s]+a[s+1]+……a[t-1]，这时，a[s+1]+a[s+1]+……a[t-2]

故可以设计如下算法：

1.初始s=t=sum=0

2.只要依然有sum

3.如果2中无法满足sum>=s则终止，否则ans=min(ans,t-s);

4.将sum减去a[s],s+=1后回到2

总复杂度为O(N)

1.二分法

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=100000+10; const int INF=0x7fffffff; int a[MAXN],sum[MAXN]; int search(int L,int R,int target) //(L,R] { while(L
     
      >1; if(sum[m]
      
       =tot -> sum[t]>=tot+sum[i] ans=min(ans,t-i); } if(ans==INF) printf(0 ); else printf(%d ,ans); } return 0; }
      
     
    
   
  

#include
  
   
#include
   
     using namespace std; const int MAXN=100000+10; const int INF=0x7fffffff; int a[MAXN]; int main() { int T; scanf(%d,&T); while(T--) { int n,tot; scanf(%d%d,&n,&tot); for(int i=0;i