【题目】
A sequence ofNpositive integers(10 <N< 100000), each of them less than or equal 10000, and a positive integerS(S<
100000000)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 toS.
Many test cases will be given. For each test case the program has to read the numbersNandS, 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.
For each the case the program has to print the result on separate line of the output file. If there isn't such a subsequence, print 0 on a line by itself.
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
2
3
【分析】
本题最直接的思路是二重循环,枚举子序列的起点和终点。代码如下(输入数据已存入数组A[1]~A[n])。
int ans = n+1;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++) {
int sum = 0;
for(int k = i; k <= j; k++) sum += A[k];
if(sum >= S) ans = min(ans, j-i+1);
}
printf("%d\n", ans == n+1 ? 0 : ans);
很可惜,上述程序的时间复杂度是O(n3)的,因此,当n达到100000的规模后,程序将无能为力。有一个方法可以降低时间复杂度,即常见的前缀和技巧。令Bi=A1+A2+…+Ai,规定B0=0,则可以在O(1)时间内求出子序列的值:Ai+Ai+1+…+Aj=Bj-Bi-1。这样,时间复杂度降为O(n2),代码如下。
B[0] = 0;
for(int i = 1; i <= n; i++) B[i] = B[i-1] + A[i];
int ans = n+1;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
if(B[j] - B[i-1] >= S) ans = min(ans, j-i+1);
printf("%d\n", ans == n+1 ? 0 : ans);
遗憾的是,本题的数据规模太大,O(n2)时间复杂度的算法也太慢。不难发现,只要同时枚举起点和终点,时间复杂度不可能比O(n2)更低,所以必须另谋他路。比如,是否可以不枚举终点,只枚举起点,或者不枚举起点,只枚举终点呢?
我们首先试试只枚举终点。对于终点j,我们的目标是要找到一个让Bj-Bi-1≥S,且i尽量大(i越大,序列长度j-i+1就越小)的i值,也就是找一个让Bi-1≤Bj-S最大的i。考虑图1-29所示的序列。
当j=5时,B5=12,因此目标是找一个Bi-1≤12-7=5的最大i。注意到B是递增的(别忘了,本题中所有Ai均为整数),所以可以用二分查找。
【代码】
/*********************************
* 日期:2014-5-14
* 作者:SJF0115
* 题号: 1121 - Subsequence
* 地址:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=246&page=show_problem&problem=3562
* 来源:UVA
* 结果:Accepted
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define N 100001
int A[N];
int B[N];
//二分查找最接近target但不大于target
int BinarySerach(int target,int R){
int L = 0;
int mid = 0;
while(L < R){
mid = L + (R - L) / 2;
if(B[mid] > target){
R = mid;
}
else{
L = mid + 1;
}
}
return L;
}
int main(){
int n,s,i,j;
//freopen("C:\\Users\\wt\\Desktop\\acm.txt","r",stdin);
while(scanf("%d %d",&n,&s) != EOF){
int minLen = n+1;
B[0] = 0;
for(i = 1;i <= n;i++){
scanf("%d",&A[i]);
//序列前缀和
B[i] = B[i-1] + A[i];
}
for(j = 1;j <= n;j++){
int target = B[j] - s;
//二分查找
int index = BinarySerach(target,j-1);
if(index > 0){
minLen = min(minLen,j-index+1);
}
}
//没有满足条件的序列
if(minLen == n+1){
minLen = 0;
}
cout<<minLen<<endl;
}//while
return 0;
}
【相似题目】
编程之美之2.14 求数组的子数组之和的最大值
分享到:
相关推荐
研究4-甲氧基-2-硝基苯胺/丙酮溶液中浓度依赖的两光子吸收和其后的激发态吸收,顾兵,Wei Ji,应用近红外飞秒脉冲激光激发下的Z-扫描和瞬态吸收测量实验,研究了4-甲氧基-2-硝基苯胺(4M2N)/丙酮溶液中浓度依赖的两...
| | | | --- Subsequent adjustment | | | | | | | | | ------Subcontracting MB04 | | | | | | | |-- Material document | | | | | | | | | |-----Change MB02 | | | | |-----Display MB03 | | | | |-----...
Licensed under the EUPL, Version 1.1 or - as soon as they will be approved by the European Commission - subsequent versions of the EUPL (the "Licence"); You may not use this work except in ...
Resolved issue 537: Manually clicking on javascript alert causes chromedriver to return UnexpectedAlertPresentException for all subsequent calls [Pri-3] Resolved issue 1: Implement /sessions command ...
to which the subsequent information pertains 2. entity ID - A unique entity node ID or NIL ID, correspondent to entity linking annotation and NIL-coreference (clustering) annotation respectively....
这个文档的质量相当高,不过是纯英文的,但是,我保证你看过之后,肯定会认为这个文档写得实在太好了。
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 ...
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...
subsequent filter circuitry. Combined with on-chip voice compression algorithms, this solution forms a cost effective and ultra-low-power base band circuit for voice communication applications.
All subsequent clicks continue to rotate through the two functions. Use unbind("click") to remove. 返回值 jQuery 参数 fn (Function) : 第奇数次点击时要执行的函数。 fn (Function) : 第偶数次点击时要...
ary of two subsequent words. Further, this paper exploits a support vector machine (SVM) classifier, which learns the segmenta- tion rules of the Chinese language from a context model of break points ...
All the subsequent gateways are used as backup when the first default gateway is discovered to be unavailable. The Dead Gateway Detection mechanism is used only with TCP (connection-oriented traffic)....
Specifically, KERP decomposes medical reportgenerationintoexplicitmedicalabnormalitygraphlearning and subsequent natural language modeling. KERP first employs an Encode module that transforms visual ...
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 ...
集合了 所有的 Unix命令大全 ...telnet 192.168.0.23 自己帐号 sd08077-you0 ftp工具 192.168.0.202 tools-toolss ... 各个 shell 可互相切换 ksh:$ sh:$ csh:guangzhou% bash:bash-3.00$ ... 命令和参数之间必需用空格隔...
An unexpected relationship between failure and subsequent mathematics learning AN UNEXPECTED RELATIONSHIP BETWEEN FAILURE AND SUBSEQUENT MATHEMATICS LEARNING JOSEPH M. SCANDURA, JOAN BARKSDALE, ...
subsequent processor generations have introduced new instruction types and formats, many compilers, including GCC, have avoided using these features in the interest of maintaining backward ...
Upgrade urgency SECURITY: See security fixes below. ...subsequent failover or node joining (redis/redis#12344) Ensure that the function load timeout is disabled during loading from RDB/AOF and on repli
Patch 16619894 - 10.2.0.5.12 Patch Set Update ... Subsequent PSU patches can be installed on Oracle Database 10.2.0.5.0 or any PSU with a lower 5th numeral version than the one being installed.
PassMark BurnInTest V5.3 ...All Rights Reserved ... Overview ======== Passmark's BurnInTest is a software tool that allows all the major sub-systems of a computer to be simultaneously tested for reliability...