自动搬运

查看原文

来自洛谷，原作者为

	2018ljw 凭君莫话封侯事，一将功成万骨枯

搬运于2025-08-24 21:59:14，当前版本为作者最后更新于2022-12-29 21:15:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题最大难度在于看出暴力复杂度是调和级数。

首先给所有单词长度和行长度均加一，简化掉对单词间空格和行末空格的处理。然后就可以贪心分段了。

可以直接前缀和二分解决，不过考虑到行长变长，行数减小，并且分段右移，所以直接对每个被分开的位置用一堆指针去维护，暴力移动、统计答案即可，如果某个指针移出界那么后面的指针就直接舍弃。

复杂度分析：不难发现复杂度与所有询问分行总数有关。假设所有单词长度均为 $l$，询问从 $l$ 到 $n$。则总数为 $l\times\frac nl+l\times\frac n{2l}+\ldots=n+\frac n2+\ldots\le n\ln n$，$l=1$ 时取等。

所以复杂度大概只有 $O(n\ln n)$ 不到。

#include<cstdio>
#include<cstring>
char s[500001];
int n,d[500001],a,b;
int sum[500001];
int p[500001],top;
int main(){
	int i,j;
	while(1){
		scanf("%s",s+1);
		if(s[1]<='9')break;
		d[++n]=strlen(s+1)+1;
	}
	int l=strlen(s+1);
	for(i=1;i<=l;i++)a=a*10+s[i]-'0';
	scanf("%d",&b);
	a++;b++;
	for(i=1;i<=n;i++)sum[i]=sum[i-1]+d[i];
	for(i=1;i<=n;i++)if(sum[i]-sum[p[top]]>a)p[++top]=i-1;
	for(i=a;i<=b;i++){
		for(j=1;j<=top;j++){
			if(p[j]<p[j-1])p[j]=p[j-1]+1;
			while(p[j]<=n&&sum[p[j]]-sum[p[j-1]]<=i)p[j]++;
			if(p[j]>n)top=j-1;p[j]--;
		}
		int res=0;
		for(j=0;j<=top;j++)res+=d[p[j]+1];
		printf("%d\n",res-1);
	}
}