[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) ;
    }
}