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) == O(n^2)注意n<=10^5 限制条件:累和大于等于S 最优评判标准:区间长度最小 |
【完整代码】: 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 }
|
【关键词】:二分,思维 |
相关文章
- 10-18面试系列(二)Android中的序列化
- 10-18128. Longest Consecutive Sequence *HARD* -- 寻找无序数组中最长连续序列的长度
- 10-18vue-ref、js获取dom子元素
- 10-18DVI输出子卡学习资料第215篇:基于FMC接口的8路LVDS输入 1路DVI输出子卡
- 10-18在子文件夹上托管Django
- 10-18Python基础--通用序列操作
- 10-187-5 求整数序列中出现次数最多的数 (20分)
- 10-185.7 进阶7:子查询
- 10-18cmd命令 拷贝某文件夹及其子文件夹文件到其它文件夹
- 10-183331=数据结构实验之链表八:Farey序列