首页 > 代码库 > POJ 3061 (二分+前缀和)
POJ 3061 (二分+前缀和)
题目链接: http://poj.org/problem?id=3061
题目大意：找到最短的序列长度，使得序列元素和大于S。
解题思路：
两种思路。
一种是二分+前缀和。复杂度O(nlogn)。有点慢。
二分枚举序列长度，如果可行，向左找小的，否则向右找大的。
前缀和预处理之后，可以O(1)内求和。
#include "cstdio"#include "cstring"int sum[100005],n,s,a,T;bool check(int x){ int l,r; for(int i=1;i+x-1<=n;i++) { l=i,r=i+x-1; if(sum[r]-sum[l-1]>=s) return true; } return false;}int main(){ //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) { scanf("%d",&a); sum[i]=sum[i-1]+a; } int l=0,r=n,ans=0; while(l<=r) { int mid=l+(r-l)/2; if(check(mid)) {ans=mid;r=mid-1;} else l=mid+1; } printf("%d\n",ans); memset(sum,0,sizeof(sum)); }}
另一种是某本著名的日译ACM书介绍的尺取法。复杂度O(n)
这个方法很简单。
①令L=1,先找一下满足要求的第一个长度（当然不一定是最优结果）。期间R++不停伸展。
②满足了是吧，现在踢掉第一个元素，令L++。从第二个元素看起，不符合要求继续伸展R。更新一下ans。继续踢第二个元素。
③踢踢踢，直到不能伸展R，且不符合要求，break。
这种方法只有一个疑问点，就是R不往回移动，其结果一定是对的吗？
考虑一下，L一直向右移动，R其实没必要向左动了。R只有在不满足条件的时候才向右，否则停在原位。
此时凭L的移动已经能找出所有可行的区间了。可以联想一下滑动变阻器，固定R，滑动L。
#include "cstdio"#include "cstring"#include "iostream"using namespace std;int a[100005],n,s,l,r,T,sum,ans;int main(){ //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--) { scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) scanf("%d",&a[i]); l=1,r=1,sum=0,ans=0x3f3f3f3f; while(true) { while(sum<s&&r<=n) sum+=a[r++]; if(sum<s) break; ans=min(ans,r-l); sum-=a[l++]; } if(ans==0x3f3f3f3f) printf("0\n"); else printf("%d\n",ans); }}
| 13592296 | neopenx | 3061 | Accepted | 548K | 79MS | C++ | 593B | 2014-11-02 20:53:32 |
POJ 3061 (二分+前缀和)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。