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

題意為：給定長(zhǎng)度為n的整數(shù)數(shù)列以及整數(shù)S，求出總和不小于S的連續(xù)子序列的長(zhǎng)度的最小值。假設(shè)解 不存在，輸出0.

第一種方法：

先求出sum[i],從第1個(gè)數(shù)到第i個(gè)數(shù)的區(qū)間和，每次固定一個(gè)開始查找的起點(diǎn)sum[i], ?然后採用二分查找找到 sum[i] + S 的位置，區(qū)間長(zhǎng)度即為（末位置-（起始位置-1）），用ans保存過程中區(qū)間的最小值。時(shí)間復(fù)雜度 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是開始查找的數(shù)的前一個(gè)位置
        {
            int t=lower_bound(sum+s+1,sum+n+1,sum[s]+S)-(sum+s);//sum+s是從第sum+s+1個(gè)地址開始查找的前一個(gè)地址，所以找到的地址減去這個(gè)地址即為區(qū)間長(zhǎng)度
            ans=min(ans,t);
        }
        printf("%d\n",ans);
    }
    return 0;
}
    

另外一種方法：尺取法

重復(fù)地推進(jìn)區(qū)間的開頭和末尾 ，來求滿足條件的最小區(qū)間的方法稱為尺取法。

主要思想為：當(dāng)a1, ?a2 ?, a3 滿足和>=S,得到一個(gè)區(qū)間長(zhǎng)度3，那么去掉開頭a1, ? 剩下 a2,a3，推斷是否滿足>=S,假設(shè)滿足，那么區(qū)間長(zhǎng)度更新，假設(shè)不滿足。那么尾部向后拓展，推斷a2,a3,a4是否滿足條件。

反復(fù)這種操作。

個(gè)人對(duì)尺取法的理解：

當(dāng)一個(gè)區(qū)間滿足條件時(shí)。那么去掉區(qū)間開頭第一個(gè)數(shù)，得到新區(qū)間。推斷新區(qū)間是否滿足條件，假設(shè)不


滿足條件。那么區(qū)間末尾向后擴(kuò)展，直到滿足條件為之。這樣就得到了很多滿足條件的區(qū)間，再依據(jù)題


意要求什么，就能夠在這些區(qū)間中進(jìn)行選擇，比方區(qū)間最長(zhǎng)，區(qū)間最短什么的。

這樣跑一遍下來。時(shí)間


復(fù)雜度為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;
}
    

另外一種方法求區(qū)間長(zhǎng)度的方法為 （末位置+1-起始位置）