題目

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
Input
The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.
Output
For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
Sample Input
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3

分析與解答

題意：給出長度為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,左端點移動，右端點不動
4.模擬過程：

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\n",res); }

ac代碼

#include <iostream> #include <algorithm> #include <cstring> #include<cstdio> using namespace std; const int mm=100010; int a[mm]; int n,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\n",res); }int main(){int t;cin>>t;while(t--){memset(a,0,sizeof(a));cin>>n>>s;for(int i=0;i<n;++i){cin>>a[i];}solve();} }

二分搜索法

我們想想，既然是連續子序列，那么可以通過前綴數組表示出所以子序列可能情況，我們只需找出滿足條件的情況，進行判斷然后輸出就可以了
對于這一題，如果在i到n中有一個t，使得sum[t]-sum[i]>=s，那t-s就是他們之間的元素個數，所以我們只需找t，利用lower_bound,
我第一次用的是這個方法，用畫圖的方法，要搞清楚他的區間

sum[i]是從1開始存的,有人問那個循環為啥是從零開始，
因為循環從零開始是找有沒有sum[i]直接就等于s了
循環從1開始的話，就正式找sum[t]了

#include <iostream> #include <algorithm> #include <cstring> #include<cstdio> using namespace std; const int mm=100010; int a[mm]; int sum[mm]; int n,s;void solve(){for(int i=0;i<n;++i){sum[i+1]=sum[i]+a[i];}if(sum[n]<s){printf("0\n");return ;}int res = n;for(int i=0;sum[i]+s<sum[n];++i){int t=lower_bound(sum+i,sum+n,s+sum[i])-sum;res=min(res,t-i);}printf("%d\n",res); }int main(){int t;cin>>t;while(t--){memset(a,0,sizeof(a));memset(sum,0,sizeof(sum));cin>>n>>s;for(int i=0;i<n;++i){cin>>a[i];}//sum[0]=0;solve();} }

總結

以上是生活随笔為你收集整理的（二分搜索法尺取法）subsequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。