[ACM] POJ 3061 Subsequence (仿真足）

Description

Input

Output

Sample Input

      2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
    

Sample Output

      2
3
    

Source

题意为：给定长度为n的整数数列以及整数S，求出总和不小于S的连续子序列的长度的最小值。假设解 不存在，输出0.

第一种方法：

先求出sum[i],从第1个数到第i个数的区间和，每次固定一个開始查找的起点sum[i],  然后採用二分查找找到 sum[i] + S 的位置，区间长度即为（末位置-（起始位置-1）），用ans保存过程中区间的最小值。时间复杂度 0(nlogn)

代码：

      #include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=100010;
int num[maxn];
int sum[maxn];
int n,S;

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&S);
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i]);
            sum[i]=sum[i-1]+num[i];
        }
        if(sum[n]<S)
        {
            cout<<0<<endl;
            continue;
        }
        int ans=maxn;
        for(int s=0;sum[s]+S<=sum[n];s++)//从sum[s+1]開始查找，s是開始查找的数的前一个位置
        {
            int t=lower_bound(sum+s+1,sum+n+1,sum[s]+S)-(sum+s);//sum+s是从第sum+s+1个地址開始查找的前一个地址，所以找到的地址减去这个地址即为区间长度
            ans=min(ans,t);
        }
        printf("%d\n",ans);
    }
    return 0;
}
    

另外一种方法：尺取法

重复地推进区间的开头和末尾 ，来求满足条件的最小区间的方法称为尺取法。

主要思想为：当a1,  a2  , a3 满足和>=S,得到一个区间长度3，那么去掉开头a1,   剩下 a2,a3，推断是否满足>=S,假设满足，那么区间长度更新，假设不满足。那么尾部向后拓展，推断a2,a3,a4是否满足条件。

反复这种操作。

个人对尺取法的理解：

当一个区间满足条件时。那么去掉区间开头第一个数，得到新区间。推断新区间是否满足条件，假设不


满足条件。那么区间末尾向后扩展，直到满足条件为之。这样就得到了很多满足条件的区间，再依据题


意要求什么，就能够在这些区间中进行选择，比方区间最长，区间最短什么的。

这样跑一遍下来。时间


复杂度为O（n)。

代码：

      #include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn=100010;
int num[maxn];
int n,S;

int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&S);
        for(int i=1;i<=n;i++)
            scanf("%d",&num[i]);
        int sum=0,s=1,e=1;
        int ans=n+1;
        for(;;)
        {
            while(e<=n&&sum<S)
                sum+=num[e++];
            if(sum<S)
                break;
            ans=min(ans,e-s);
            sum-=num[s++];
        }
        if(ans==n+1)
            cout<<0<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}
    

另外一种方法求区间长度的方法为 （末位置+1-起始位置）