2015年4月9日 星期四

[USACO 2014 Gold] Airplane Boarding

作法:

先看第 n 隻牛,他在時間 0 的時候位於 x=0 ,並且在時間 S[ n ] 時走到自己位置, S[ n ] + T[ n ] 時坐下。而這就帶給了第 n-1 隻牛一個限制:必須要等到時間為 S[ n ] +T[ n ] + 1 時他才有辦法走到 S[ n ] 。所以當我們處理每隻牛的時候,假設對這隻牛的限制為 ( a_1 , b_1 ) , ... , ( a_r , b_r ) ,其中 ( a , b ) 代表至少要等到 b 秒時才可以走到 a 位置,那麼這隻牛走到目的地的時間就會是: max{ b_i + ( S - a_i ) },其中 a_i 滿足 a_i <= S 。也就是我們會需要查詢在所有第一個座標 <= S 的限制中, b - a 最大的數是多少。所以現在可以得到這樣的算法:按照 n ~ 1 的順序處理每隻牛,一開始的限制就只有 ( 0 , 0 ) ,然後對於每個正在處理的牛 i ,掃一遍目前所有的限制,把 a 值 <= S[ i ] 的限制們的 b-a 值拿去更新最大值,算出這隻牛坐好的時間 U[ i ] ,並且這會代表第 i-1 隻牛至少要等到 U[ i ] +1 才可以走到 S[ i ] ,也就是多把 ( S[ i ] , U[ i ] +1 ) 加入限制中。但還要注意到的是,如果 ( a , b ) 滿足 a <= S[ i ] ,代表第 i 隻牛至少要到時間 b 才可以走到 a 位置,那麼這件事對第 i-1 隻牛來說就會變成:他至少要到時間 b 才可以走到 a-1 位置,因為他會被第 i 隻牛擋住,而對於那些 a > S[ i ] 的限制們則不用更新。所以我們必須要在算完 i 的答案時,對所有 a <= S[ i ] 的限制們都更新一次,這樣就得到了 O(n^2) 的演算法。

至於要如何優化成O(nlogn) ,首先要注意到:如果有兩個限制 ( a , b ) 和 ( c , d ) ,滿足 c > a 且 d-c < b-a ,那麼 ( c , d ) 這個限制就廢掉了,因為當 c <= S[ i ] 時 a 必定也 <= S[ i ] ,他永遠不會比 ( a , b ) 更好,也就是在我們維護的限制們裡,當 a 遞增時 b-a 也是遞增的,所以每次加入一個新的限制 ( a , b ) 時要再把所有廢掉的 ( c , d ) 都砍掉。雖然這個觀察還是會得到O(n^2) 算法,但是這樣就會發現可以用 treap 維護所有的限制。使用分裂合併式的 treap ,並且對每個限制都記錄他的 a 值和 b-a 值,還有這棵子樹中 b-a 的最大值,而且我們會需要區間加值的動作,所以會需要再記個 tag 值。當要詢問的時候只要把 a <= S[ i ] 的那一部分切下來問問就好了,並且在砍掉不必要的 ( c , d ) 時,可以很方便的直接從剛剛切完得到的右子樹中,直接把 b-a 值太小的節點都切掉( 因為當 a 遞增時 b-a 也遞增,所以單看 b-a 的話他也還是一個treap ),並且在「對於 a<=S[ i ] 的限制,都把 a 值減一」的操作時只要對左子樹打個標記就好了,最後再把領個更新完的子樹黏起來即可。

code :



#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
struct node
{
    node *l,*r ;
    int x,y ;
    int val,tag,fix ;
    node(int _x,int _y)
    {
        l=r=NULL ;
        x=_x ; y=_y ;
        val=y ;
        tag=0 ;
        fix=rand() ;
    }
};
 
void push(node *u)
{
    if(!u || !u->tag) return ;
    if(u->l)
    {
        u->l->x -= u->tag ;
        u->l->y += u->tag ;
        u->l->tag += u->tag ;
        u->l->val += u->tag ;
    }
    if(u->r)
    {
        u->r->x -= u->tag ;
        u->r->y += u->tag ;
        u->r->tag += u->tag ;
        u->r->val += u->tag ;
    }
    u->tag=0 ;
}
 
void pull(node *u)
{
    if(!u) return ;
    u->val=u->y ;
    if(u->l) u->val=max(u->val,u->l->val) ;
    if(u->r) u->val=max(u->val,u->r->val) ;
}
 
node *merge(node *a,node *b)
{
    if(!a || !b) return a ? a : b ;
    if(a->fix < b->fix)
    {
        push(a) ;
        a->r=merge(a->r,b) ;
        pull(a) ;
        return a ;
    }
    else
    {
        push(b) ;
        b->l=merge(a,b->l) ;
        pull(b) ;
        return b ;
    }
}
 
void split(node *u,node *&a,node *&b,int k)
{
    if(!u) { a=b=NULL ; return ; }
    push(u) ;
    if(u->x <= k)
    {
        a=u ;
        split(u->r,a->r,b,k) ;
        pull(a) ;
    }
    else
    {
        b=u ;
        split(u->l,a,b->l,k) ;
        pull(b) ;
    }
}
 
void split2(node *u,node *&a,node *&b,int k)
{
    if(!u) { a=b=NULL ; return ; }
    push(u) ;
    if(u->y <= k)
    {
        a=u ;
        split2(u->r,a->r,b,k) ;
        pull(a) ;
    }
    else
    {
        b=u ;
        split2(u->l,a,b->l,k) ;
        pull(b) ;
    }
}
 
int p[maxn],t[maxn],n ;
node *root=NULL ;
main()
{
    if(fopen("boarding.in","r"))
    {
        freopen("boarding.in","r",stdin);
        freopen("boarding.out","w",stdout);
    }
    srand(time(NULL)) ;
    scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i],&t[i]) ;
 
    int ans=0 ;
    root=merge(root,new node(0,0)) ;
    for(int i=n;i>=1;i--)
    {
        node *a,*b,*c ;
        split(root,a,b,p[i]) ;
        int val=a->val+p[i]+t[i] ;
        ans=max(ans,val) ;
        a->tag++ ; a->x-- ; a->y++ ; a->val++ ;
        split2(b,b,c,val+1-p[i]) ;
        root=merge(merge(a,new node(p[i],val+1-p[i])),c) ;
    }
    printf("%d\n",ans) ;
}
 
 

沒有留言:

張貼留言