P4347 题解

2018ljw · 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);
    }
}