Description：

一个序列，元素都是属于 $[0,k)$ 的整数。 每次选择一个区间 $+1\%k$ ，求最少需要多少次才能将所有元素都变成 $0$ 。

$1\leqslant n\leqslant 10^7,2\leqslant k\leqslant 4$

Solution：

首先肯定差分得到 $b[]$ ， $c[i]$ 表示 $b[i]$ 被加了几，就是说 $i$ 每作为一次左端点 $c[i]$ 就 $+1$ ，每作为一次右端点 $c[i]$ 就 $-1$ 。那么有一个初始解 $c_0[i]=(k-b[i])\%k$ ，那么最终 $c[i]$ 一定为 $c_0[i]$ 或 $c_0[i]-k$ ，要求 $c[i]$ 的前缀和必须永远不为负才合法，那么最后的答案就是所有大于零的 $c[i]$ 之和，那么考虑一次 $-k$ 操作，对于 $c[i]$ 不同的我们肯定优先减 $c[i]$ 大的，因为他们对前缀和的影响相同，而减大的更合算，对于 $c[i]$ 相同的我们肯定先减靠后的，因为对前缀和的影响小，按照这个贪心即可，时间复杂度 $O(nk)$ ，如果用数据结构维护可以做到 $O(n\log n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 10000010

int a[MAXN],v[MAXN];

int s[MAXN];

int main()

{

	freopen("modulo.in","r",stdin);

	freopen("modulo.out","w",stdout);

	scanf("%d",&k);

	char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		a[++n] = c - '0';

		s[n] = (a[n] - a[n - 1] + k) % k;

		c = getchar();

	}

	for(int i = n;i >= 1;--i)a[i] = (a[i] - a[i - 1] + k) % k;

	for(int i = 1;i <= n;++i)v[i] = (k - a[i]) % k;

	for(int i = 1;i <= n;++i)s[i] = s[i - 1] + v[i];

	int ans = s[n];

	for(int x = k - 1;x >= 1;--x)

	{

		int minsum = 0x3f3f3f3f;

		for(int i = n;i >= 1;--i)

		{

			minsum = min(minsum,s[i]);

			if(v[i] == x && minsum >= k)

			{

				ans -= v[i];minsum -= k;

				v[i] -= k;

			}

		}

		for(int i = 1;i <= n;++i)s[i] = s[i - 1] + v[i];

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}