UVALive2678子序列

UVALive2678

http://122.207.68.93:9090/csuacmtrain/problem/viewProblem.action?id=453

【题目描述】:n个正整数组成的序列。给定整数S,求长度最短的连续序列,使他们的和大于等于S

【算法分析】:

【二分】:

全是正整数,保证取的连续序列长度越长,和越可能大于等于S,所以满足二分的单调递增的条件,而这里,我们要找的最优解是最小的长度,就是和刚刚好大于等于S的区间长度。

【区间和优化到O(N)】:

使用C[i]数组,做差求和。方法不细说。要求自己,以后遇到区间求和问题,自然就要想到这个。

【运筹分析】:

决策方案:所有区间段,sigm(n+(n-1).......+1) == On^2)注意n<=10^5

限制条件:累和大于等于S

最优评判标准:区间长度最小

【完整代码】:

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 }
UVALive2678子序列

 

 

【关键词】:二分,思维

UVALive2678子序列

上一篇:NTP Reply Flood Attack (NTP反射型DDos攻击)


下一篇:USB设备的插入检测