尺取法及应用 - POJ 3061

尺取法及其应用 - POJ 3061

简介

返回推进区间的开头和结尾，求满足条件的最小区间的方法称为尺取法。，顾名思义，就是像一把尺子（固定某一条件），不断向右（左）移动，不断更新所求答案。一般用来求满足条件的最小区间。

主要实现方法为：

1. 初始化左右端点
2. 不断扩大右端点，直至满足条件
3. 如果直至终点也无法满足条件，则终止，否则更新结果
4. 扩大左端点（右移1），跳回步骤2

这种方法只有一个疑问点，就是R不往回移动，其结果一定是对的吗？

考虑一下，L一直向右移动，R其实没必要向左动了。R只有在不满足条件的时候才向右，否则停在原位。

此时凭L的移动，已经能找出所有可行的区间了。

例题

例题链接：http://poj.org/problem?id=3061

找到最短的序列长度，使得序列元素和大于S。

在这道题中，序列都是正数，如果一个区间其和大于等于S，那么不需要在向后推进右端点了，因为其和也肯定大于等于S但长度更长。

所以，当区间和小于S时右端点向右移动，和大于等于S时，左端点向右移动以进一步找到最短的区间。

如果右端点移动到区间末尾其和还不大于等于S，结束区间的枚举。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int t,n,s;
int a[maxn];
int main()
{
    ios::sync_with_stdio(false);  //加速流
    cin>>t;
    while(t--)
    {
        cin>>n>>s;
        for(int i=0; i<n; i++)
            cin>>a[i];
        int l=0,r=0,ans=n+1;   //l，r:左右端点  ans初始值设为n+1
        int sum=0;
        while(true)
        {
            while(r<n&&sum<s)
                sum+=a[r++];
            if(sum<s)         //如果所有数的和都小于s，直接跳出循环
                break;
            ans=min(ans,r-l); //此时r一定小于n
            sum-=a[l++];      //去掉最左端点，继续前进
        }
        if(ans==n+1)
            cout<<0<<endl;
        else
            cout<<ans<<endl;
    }
}

网上说还可以结合前缀和来思考解法。