国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

尺取法

2019-11-11 04:33:48
字體:
來源:轉載
供稿:網友

例題:POJ 3061


Subsequence

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 13348 Accepted: 5635

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

210 155 1 3 5 10 7 4 9 2 85 111 2 3 4 5

Sample Output

23

Source

Southeastern Europe 2006


#include<iostream>#include<cstdio>#define min(a,b) (a<b?a:b)#define max(a,b) (a>b?a:b)using namespace std;const int MAXN=1e5;int N,S;int a[MAXN+1];int num;void solve(){ int res=N+1; int s=0,t=0,sum=0; while(true) { while(t<N&&sum<S) sum+=a[t++]; if(sum<S) break; res=min(res,t-s); sum-=a[s++]; } if(res>N) res=0; cout<<res<<endl;}int main(){ cin>>num; for(int tmp=1;tmp<=num;tmp++) { int i=1; cin>>N>>S; for(i=1;i<=N;i++) cin>>a[i]; solve(); } return 0;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 化德县| 泽普县| 北票市| 织金县| 彝良县| 尉犁县| 枣庄市| 西充县| 建昌县| 庐江县| 左贡县| 南丹县| 舒城县| 双鸭山市| 柳林县| 广丰县| 新乡市| 怀宁县| 玉溪市| 赫章县| 来宾市| 彩票| 简阳市| 浦北县| 荥阳市| 宁安市| 商洛市| 上虞市| 浪卡子县| 安吉县| 江永县| 扬中市| 新乡市| 乌鲁木齐市| 锡林浩特市| 鄂州市| 淮滨县| 巴彦县| 丰镇市| 桦甸市| 三河市|