2015年4月18日 星期六

[CF 526E] Transmitting Levels

作法:

對於每個點,我們可以預處理出「從他開始往後取,最多可以取到哪個數」,也就是對 i 來說,設 j 是最小的滿足 a[ i ] + ... + a[ j ] > B 的數 ( j 如果跑超過 n 了就從 1 繼續跑,因為他是環在一起的),對每個 i 都算出這樣的 j ,把他叫作 nex[ j ]。首先可以得到:一定有一個切點存在於 i , i+1 之間,或 ... 或 j-1, j 之間,否則如果這些地方都沒有切點的話,代表 i ~ j 都在同一塊,就矛盾了。因此可以想到第一個算法:隨便選一個 i ,那麼就枚舉剛剛那些可能的切點,因為只要確定了一個切點,就可以把問題轉成一維問題了。因為只要一直沿著 nex 陣列往後跳,跳到第一個超出去的時候就會得到答案了。但這樣複雜度會爛掉,而這只要加上一個優化就可以了:考慮 nex[ i ] 和 i 的距離(也就是 i 走幾步才會走到 nex[ i ]),那麼只要挑讓這個距離最小的 i 就可以了,因為如果這個距離為 d 的話,那麼枚舉的時候只會枚舉 d 次,而每次枚舉的時候,因為跳的長度都會 >= d ,所以跳 O(n / d) 次就會回來了,因此複雜度就會是好的 O( d ) * O( n / d ) = O( n ) 。

code :



#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000000+10 ;
 
int n,a[maxn],len[maxn] ;
int dis(int x,int y)
{
    if(y>=x) return y-x ;
    return n+y-x ;
}
 
LL s[2*maxn] ;
main()
{
    int Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<=2*n;i++) s[i]=s[i-1]+(i>n?a[i-n]:a[i]) ;
    while(Q--)
    {
        LL x ; scanf("%lld",&x) ;
        if(x>=s[n]) { printf("1\n") ; continue ; }
        int id,mi=n+1 ;
        for(int i=n,j=2*n-1;i>=1;i--)
        {
            while(s[j]-s[i-1]>x) j-- ;
            len[i]=min(n,j-i+1) ;
            //printf("len[%d]=%d\n",i,len[i]) ;
            if(len[i]<mi) mi=len[id=i] ;
        }
 
        int ans=n ;
        for(int i=id;i<=id+len[id];i++)
        {
            int cnt=0 , st=(i-1)%n+1 ;
            for(int j=st;!cnt || dis(j,st)>len[j];
                j=(j+len[j]-1)%n+1,cnt++) ;
            ans=min(ans,cnt+1) ;
        }
        printf("%d\n",ans) ;
    }
}
 

沒有留言:

張貼留言