题解 P3575 【[POI2014]DOO-Around the world】

· · 题解

先断环成链复制一遍，再前缀和预处理

显然终点都在[n+1,2n]中，把终点当作起点倒推

考虑设走f[i]步可以到达的最远的点为fa[i]

如果当前所在点为i，找到可以到达的最远的点为j

那么f[i]=f[j]+1，fa[i]=fa[j]

如果i-fa[i]>=n，那么直接退出输出f[i]

因为不存在一个更靠后的位置答案更优，证明不会

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000002;
int m,n,x,s,f[maxn],fa[maxn],sum[maxn];
inline int read () {
    char ch=getchar(); int num=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch^'0'),ch=getchar();
    return num;
}
int main () {
    n=read(),s=read();
    for(register int i=1;i<=n;++i) {
        int x=read(); m=max(m,x);
        fa[i]=i,sum[i]=sum[i-1]+x;
    }
    for(register int i=n+1;i<=(n<<1);++i)
        sum[i]=sum[i-1]+sum[i-n]-sum[i-n-1];
    while(s--) {
        register int i,j,d=read();
        if(d<m) puts("NO");
        else for(i=n+1,j=1;i<=(n<<1);++i) {
            while(sum[i]-sum[j]>d) ++j;
            f[i]=f[j]+1,fa[i]=fa[j];
            if(i-fa[i]>=n) {
                printf("%d\n",f[i]);
                break ;
            }
        }
    }
    return 0;
}