题目链接: http://poj.org/problem?id=3061
题目大意：找到最短的序列长度，使得序列元素和大于S。
解题思路：
两种思路。
一种是二分+前缀和。复杂度O(nlogn)。有点慢。
二分枚举序列长度，如果可行，向左找小的，否则向右找大的。
前缀和预处理之后，可以O(1)内求和。
#include "cstdio"
#include "cstring"
int sum[],n,s,a,T;
bool check(int x)
{
int l,r;
for(int i=;i+x-<=n;i++)
{
l=i,r=i+x-;
if(sum[r]-sum[l-]>=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=;i<=n;i++)
{
scanf("%d",&a);
sum[i]=sum[i-]+a;
}
int l=,r=n,ans=;
while(l<=r)
{
int mid=l+(r-l)/;
if(check(mid)) {ans=mid;r=mid-;}
else l=mid+;
}
printf("%d\n",ans);
memset(sum,,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[],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=;i<=n;i++) scanf("%d",&a[i]);
l=,r=,sum=,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 |