爱站程序员基地题目来源：poj-3061
Subsequence
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 32107 Accepted: 13432
Description
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
时间复杂度
o(n)
代码
#include <iostream>//#include<bits/stdc++.h>using namespace std;typedef long long int ll;int ai[100010];int main(){ios::sync_with_stdio(false);cin.tie(0);int t;cin>>t;for(int i=1;i<=t;i++){int n,s;cin>>n>>s;for(int j=1;j<=n;j++){cin>>ai[j];}int l=1,r=2,flag=0,tol=ai[1]+ai[2],minn;//printf(\":%d\\n\",tol);while(l<r&&l<=n&&r<=n){//printf(\"%d %d %d\\n\",l,r,tol);if(tol>=s){if(flag==0){flag=1;minn=r-l+1;}else{minn=min(minn,r-l+1);}tol-=ai[l];l++;}else if(tol<s){r++;tol+=ai[r];}}if(flag){cout<<minn<<endl;}else{cout<<0<<endl;}}return 0;}
思路
先定义一个left，一个right的标记，left初始化赋值为1，rightchushihua赋值为2，sum是left到right之间的和，如果sum>=s,那么left就要增加一位，看看left增加一位后是不是还大于等于s，同理如果sum<s，right就要增加一位，同时要保证left始终小于right。
类似题目
问题 A: 数学 (math)
时间限制: 1 Sec 内存限制: 128 MB
题目描述
定义：f(x)为x分解为连续正整数（大于一个）的和的方案数。
例如：
·6=1+2+3，所以f（6）=1 。
·15=1+2+3+4+5=4+5+6=7+8，所以f(15)=3 。
现在输入一个正整数n，请求出f(n)。
输入
一行一个正整数，表示n。
输出
一行一个数，表示f(n)。
样例输入 Copy
15
样例输出 Copy
3
注意：
这道题需要看n的范围，我做的时候n是开到了10的12次方，所以用这种方法是不可行的，需要用另一种更适合这道题的方法。
