2016年1月20日 星期三

[TIOJ 1841][POI 21 Stage 1]好.傳囉! Nice Boat!

(題號打錯所以只好重發文章@@,順便套用剛學的latex語法)
因為HOJ在我寫完這題之後的submissions都沒有動靜(聽說HOJ快要壽終正寢了,好難過QAQ),所以現在來寫TIOJ了XD

這題題目敘述有點雜,還誤會題目意思打錯code,花了不少時間才理解成功@@
就是,給你一個數列,求最長區間的長度,使得這個區間的任意前綴和後綴和都$\geq 0$

首先,區間的任意前綴和後綴和都是區間和,可以用數列的前綴和(不是區間的)相減求得
假設一開始的$0$也算進去的話,我們可以把這些前綴和畫成有$N+1$個點的折線圖

而假設有一個區間符合題目的條件,把它對應到折線圖上面
那麼仔細思考就可以發現,在折線圖的這個區間裡面,區間左端是最低點,右端是最高點,中間不會允許任何一個點突破兩端的極值(不然就會有區間前綴或後綴和$<0$了)

為了方便說明,定義規則1為區間中間的值必須$\leq$右端點,規則2為區間中間的值必須$\geq$左端點
我們可以先預處理出每個左端點$u$符合規則2中最右邊的右端點$R[u]$,可以用單調對列實現。可以證明,在左端點到$R[u]$之間的所有點,都會是符合規則2的右端點
再來,對於每個左端點,可以維護一個符合規則1的右端點的集合,這一樣可以用單調對列從右到左掃實現
這樣,當左端點維護到$u$時,我們就可以在這個集合裡面進行二分搜,在符合規則1的右端點之中找出最大且$\leq R[u]$的點$v$,那麼$[u,v]$就是符合題目要求中左端點是$u$的最長區間了
在這些計算結果中,取最大的區間長度即可

時間複雜度:$O(N\log N)$

code:
#include<cstdio>
#include<vector>
#include<cassert>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
void getmax(int &a,const int b){if(b>a)a=b;}
struct Stack
{
    vector<int>data;
    int last;
    void clear(){data.clear(),last=-1;}
    void push(const int v){data.push_back(v),last++;}
    void pop(){data.pop_back(),last--;}
    int top()const{return data[last];}
    int lower_bound(const int v)
    {
        int l=0,r=last+1;
        while(l<r)
        {
            const int mid=(l+r)/2;
            if(data[mid]>=v)l=mid+1;
            else r=mid;
        }
        assert(r<=last);
        return data[r];
    }
}STK;
int N;
LL SUM[1000002];
int RIGHT[1000001];
int main()
{
//    freopen("in.txt","r",stdin);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d",&N);
        SUM[0]=0LL;
        for(int i=1;i<=N;i++)scanf("%lld",&SUM[i]),SUM[i]+=SUM[i-1];
        STK.clear();
        SUM[N+1]=-INF,STK.push(N+1);
        for(int i=N;i>=0;i--)
        {
            while(SUM[i]<=SUM[STK.top()])STK.pop();
            RIGHT[i]=STK.top();
            STK.push(i);
        }
        int ans=0;
        STK.clear();
        SUM[N+1]=INF,STK.push(N+1);
        for(int i=N;i>=0;i--)
        {
            while(SUM[i]>SUM[STK.top()])STK.pop();
            STK.push(i);
            getmax(ans,STK.lower_bound(RIGHT[i])-i);
        }
        printf("%d\n",ans);
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原