记录编号	608213	评测结果	AAAAAAAAAA
题目名称	4077.小b爱取模	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	1.697 s
提交时间	2025-10-24 15:25:51	内存使用	63.51 MiB

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e7 + 5;
int k, n, d[MAXN], sum[MAXN];
string s;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> k >> s;
    n = s.size();
    for(int i = 1;i <= n;i ++){
        int f = (i == 1) ? 0 : (s[i - 2] - '0');
        int u = s[i - 1] - '0';
        int df = (u - f + k) % k;
        d[i] = (k - df) % k;
    }

    for(int val = k - 1;val >= 0;val--){
        sum[0] = 0;
        for(int i = 1;i <= n;i ++) sum[i] = sum[i - 1] + d[i];
        int minx = INT_MAX;
        for(int i = n;i >= 1;i --){
            minx = min(minx, sum[i]);
            if(minx >= k && d[i] == val){
                d[i] -= k;
                minx -= k;
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i ++) ans += max(d[i], 0);
    cout << ans << '\n';
    return 0;
}