国产探花免费观看_亚洲丰满少妇自慰呻吟_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;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 阳泉市| 洛宁县| 库车县| 贡山| 嵊泗县| 通城县| 团风县| 吴江市| 万州区| 泽州县| 彩票| 梅河口市| 萨嘎县| 北川| 家居| 札达县| 望城县| 社旗县| 井冈山市| 凤城市| 兰州市| 分宜县| 麻城市| 宁强县| 平阳县| 布拖县| 永安市| 洛南县| 航空| 怀安县| 东至县| 阿克陶县| 建德市| 庆云县| 武邑县| 万宁市| 塔城市| 尉氏县| 荥经县| 客服| 北票市|