记录编号	597338	评测结果	AAAAAAAAAA
题目名称	小b爱取模	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	2.319 s
提交时间	2024-11-26 20:06:57	内存使用	90.29 MiB

#include<bits/stdc++.h>
using namespace std;
int k,n,b[10000010],c[10000010],s[10000010],ans;
char str[10000010];
int main()
{
	freopen("changgao_modulo.in","r",stdin);
	freopen("changgao_modulo.out","w",stdout);
    scanf("%d",&k);
    scanf("%s",str+1);
	str[0]='0';
	n=strlen(str+1);
	for(int i=1;i<=n;i++)
	{
		b[i]=(str[i]-str[i-1])%k;
	}
    for(int i=1;i<=n;i++)
	{
		c[i]=(k-b[i])%k;
	}
    for(int i=1;i<=n;i++)
	{
		s[i]=c[i]+s[i-1];
	}
    for(int x=k-1;~x;x--)
	{
		int mi=1e9;
        for(int i=n;i>=1;i--)
		{
            mi=min(mi,s[i]);
            if(mi>=k&&c[i]==x)
			{
				mi-=k;
				c[i]-=k;
			}
        }
        for(int i=1;i<=n;i++)
		{
			s[i]=s[i-1]+c[i];
		}
    }
	for(int i=1;i<=n;i++)
	{
		ans+=max(c[i],0);
	}
	printf("%d",ans);
	return 0;
}