Subsequence
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8427 | Accepted: 3281 |
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
题意:
给出 t 个 case,后给出 n (0 ~ 100000)个数 和 m 总和。求最小的序列长度,这个序列内的数的总和大于等于 m。输出这个长度。如果找不到则输出 0。
思路:
尺取法。反复推进区间的开头和末尾来求取满足条件的最小区间。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int MAX = 500000; int num[100005]; int main() { int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d%d", &n, &m); int len = MAX, sum = 0, from = 1; for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); sum += num[i]; if (sum >= m) { while (sum - num[from] >= m && from <= i) { sum -= num[from]; ++from; } len = min(len, i - from + 1); } } if(len == MAX) printf("0\n"); else printf("%d\n", len); } return 0; }
相关推荐
研究4-甲氧基-2-硝基苯胺/丙酮溶液中浓度依赖的两光子吸收和其后的激发态吸收,顾兵,Wei Ji,应用近红外飞秒脉冲激光激发下的Z-扫描和瞬态吸收测量实验,研究了4-甲氧基-2-硝基苯胺(4M2N)/丙酮溶液中浓度依赖的两...
这个文档的质量相当高,不过是纯英文的,但是,我保证你看过之后,肯定会认为这个文档写得实在太好了。
DataWindow Programmer’s Guide,This publication pertains to Sybase database management software and to any subsequent release until otherwise indicated in new editions or technical notes. Information...
An unexpected relationship between failure and subsequent mathematics learning AN UNEXPECTED RELATIONSHIP BETWEEN FAILURE AND SUBSEQUENT MATHEMATICS LEARNING JOSEPH M. SCANDURA, JOAN BARKSDALE, ...
The evolving investment climate in Vietnam and subsequent challenges to foreign investors 735 The Evolving Investment Climate in Vietnam and Subsequent Challenges to Foreign Investors Clifford J. ...
Relationship of WPPSI and subsequent metropolitan achievement test scores in head-start children RELATIONSHIP OF WPPSI AND SUBSEQUENT METROPOLITAN ACHIEVEMENT TEST SCORES I N HEAD-START CHILDREN ...
Parental anxiety, language, assertion, and expectation factors in subsequent understanding and recall of assessment information Psychology in rhe Schools Volume 28, April 1991 PARENTAL ANXIETY, ...
employed to model subsequent anisotropic behavior of metallic sheet. However, it might be difficult to take into account the influence of strain path change with this method. In this paper, a new ...
Verilog® HDL: A Guide to Digital Design and Synthesis, Second Edition By Samir Palnitkar Publisher : Prentice Hall PTR Pub Date : February 21, 2003 ISBN : 0-13-044911-3 Pages : 496
• The RT288x_SDK package contains the subsequent directories. o toolchain : mips toolchain o source : Linux kernel source o tools :useful script • The source directory contains the subsequent ...
• The RT288x_SDK package contains the subsequent directories. o toolchain : mips toolchain o source : Linux kernel source o tools :useful script • The source directory contains the subsequent ...
• The RT288x_SDK package contains the subsequent directories. o toolchain : mips toolchain o source : Linux kernel source o tools :useful script • The source directory contains the subsequent ...
• The RT288x_SDK package contains the subsequent directories. o toolchain : mips toolchain o source : Linux kernel source o tools :useful script • The source directory contains the subsequent ...
Freeze drying and frozen preservation way was used to preserve a moderately thermophilic culture for bioleaching of chalcopyrite concentrate. After preservation of 15 months, the cell viability rate ...
All changes and new features are subject to further change and/or withdrawal in subsequent alpha and beta releases, leading up to final release. Do not assume that databases created by or upgraded to...
that pass the first time they are run, then fail on subsequent run. The first run generated files which breaks subsequent runs. To deal with these issues, programmers usually introduce a level of ...
2. 实验步骤 1.data subsequent items stored in data segment at next available asddres
NOTE: VRTK v3 has been superseded by VRTK v4 and the subsequent Tilia packages. VRTK v3 does not work in newer versions of Unity (2020 or above) or with the latest 3rd party vendor SDK (SteamVR, ...
all subsequent releases until otherwise indicated in new editions. This edition replaces SC09-4949-05. Make sure that you use the correct edition for the level of the program listed above. Also, ...
Our argument is based on considerations of parameter interpretation and subsequent Bayesian analysis, within the context of fitting normal-error linear models. Numerical examples are used to ...