自动搬运

查看原文

来自洛谷，原作者为

	RicardoShips 王の血は剣の終わりになる

搬运于2025-08-24 21:50:20，当前版本为作者最后更新于2019-07-17 09:53:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

显然终点都在$[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;
}