ACM PKU 3061 Subsequence

http://acm.pku.edu.cn/JudgeOnline/problem?id=3061 


Subsequence 
Time Limit:1000MS  Memory Limit:65536K 
Total Submit:2626 Accepted:833 
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 

不知道为什么这道题在Discuss里被骂得体无完肤 
http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=3061 


注意细节很重要啊!我至少调试了两个小时才AC!! 

Source
Problem Id:3061  User Id:lnmm 
Memory:464K  Time:31MS 
Language:C++  Result:Accepted 
Source 
 1#include"stdio.h" 
 2int a[100010]; 
 3void main() 
 4{ 
 5long sum,N,S,min; 
 6long left,right,r;  //left 左游标，right 右游标, r向右扩展游标 
 7int T,i; 
 8scanf("%d",&T); 
 9       for(i=1;i<=T;i++) 
10    { 
11  sum=0; 
12        scanf("%ld%ld",&N,&S); 
13        for(r=1;r<=N;r++) 
14  { 
15   scanf("%ld",&a[r]); 
16   sum+=a[r]; 
17  } 
18   min=100001; 
19  if(sum<S) 
20  { 
21   min=0; 
22  } 
23         sum=0; 
24         right=0; 
25    a[0]=0; 
26   //初始化完成 
27
28
29  for(left=1;left<=N;left++) 
30  { 
31   sum=sum-a[left-1]; 
32   if(sum >= S)   
33            {     
34                if(right-left+1 < min  ) min=right-left+1;   
35                continue;   
36                }   
37             for(r=right+1;r<=N;r++) 
38    { 
39     sum=sum+a[r]; 
40     if(sum>=S) 
41     {   if(r-left+1 < min) min=r-left+1; 
42                       right=r; 
43      break; 
44     } 
45    } 
46  } 
47
48  printf("%d\n",min);   
49    } 
50
51return ; 
52}

posted on 2007-09-14 02:02 流牛ζ木马 阅读(669) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2007年9月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

导航

统计

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜