UVALive2678子序列

 1 #include<iostream>
 2 
 3 #include<stdio.h>
 4 
 5 #include<string.h>
 6 
 7 #include<algorithm>
 8 
 9 #include<stdlib.h>
10 
11 #include<math.h>
12 
13 #include<queue>
14 
15 #include<vector>
16 
17 #include<map>
18 
19 #define MAXN 100000+5
20 
21 #define MAXM 20000+5
22 
23 #define oo 9556531
24 
25 #define eps 0.000001
26 
27 #define PI acos(-1.0)//这个精确度高一些
28 
29 #define REP1(i,an) for(int i=0;i<=(n);i++)
30 
31 #define REP2(i,n) for(int i=1;i<=(n);i++)
32 
33 using namespace std;
34 
35 //这道题不是dp，而是二分，一是因为dp本身会超时，二是连续的状态是单调递增的
36 
37 int A[MAXN];
38 
39 int C[MAXN];
40 
41 int n,s;
42 
43 bool isok(int l)
44 
45 {
46 
47     for(int i=l;i<=n;i++)
48 
49     if(C[i]-C[i-l]>=s) return true;//优化到O（n）
50 
51     return false;
52 
53 }
54 
55 int main()
56 
57 {
58 
59     while(cin>>n>>s)
60 
61     {
62 
63         C[0]=0;
64 
65         for(int i=1;i<=n;i++)
66 
67         {
68 
69             cin>>A[i];
70 
71             C[i]=C[i-1]+A[i];
72 
73         }
74 
75         int l=1,r=n+1;
76 
77         while(l<r)//边界条件，保证能够跳出循环，找不到极值也可，画状态图确定
78 
79         {
80 
81             int m=(l+r)/2;
82 
83             if (isok(m)) r=m;else l=m+1;//根据除2取左的特点，保证能取到极值点
84 
85         }
86 
87         if (isok(l)) cout<<l<<endl;else cout<<0<<endl;
88 
89     }
90 
91     return 0;
92 
93 }