UVALive2678子序列

UVALive2678

http://122.207.68.93:9090/csuacmtrain/problem/viewProblem.action?id=453§

【題目描述】：n個正整數組成的序列。給定整數S，求長度最短的連續序列，使他們的和大于等于S。

【算法分析】：

【二分】：

全是正整數，保證取的連續序列長度越長，和越可能大于等于S，所以滿足二分的單調遞增的條件，而這里，我們要找的最優解是最小的長度，就是和剛剛好大于等于S的區間長度。

【區間和優化到O(N)】：

使用C[i]數組，做差求和。方法不細說。要求自己，以后遇到區間求和問題，自然就要想到這個。

【運籌分析】：

決策方案：所有區間段，sigm(n+(n-1).......+1)?==?O（n^2）注意n<=10^5

限制條件：累和大于等于S

最優評判標準：區間長度最小

【完整代碼】：

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<stdlib.h>

#include<math.h>

#include<queue>

#include<vector>

#include<map>

#define MAXN 100000+5

#define MAXM 20000+5

#define oo 9556531

#define eps 0.000001

#define PI acos(-1.0)//這個精確度高一些

#define REP1(i,an) for(int i=0;i<=(n);i++)

#define REP2(i,n) for(int i=1;i<=(n);i++)

using namespace std;

//這道題不是dp，而是二分，一是因為dp本身會超時，二是連續的狀態是單調遞增的

int A[MAXN];

int C[MAXN];

int n,s;

bool isok(int l)

{

    for(int i=l;i<=n;i++)

    if(C[i]-C[i-l]>=s) return true;//優化到O（n）

    return false;

}

int main()

{

    while(cin>>n>>s)

    {

        C[0]=0;

        for(int i=1;i<=n;i++)

        {

            cin>>A[i];

            C[i]=C[i-1]+A[i];

        }

        int l=1,r=n+1;

        while(l<r)//邊界條件，保證能夠跳出循環，找不到極值也可，畫狀態圖確定

        {

            int m=(l+r)/2;

            if (isok(m)) r=m;else l=m+1;//根據除2取左的特點，保證能取到極值點

        }

        if (isok(l)) cout<<l<<endl;else cout<<0<<endl;

    }

    return 0;

}

?

?

【關鍵詞】：二分，思維