题目大意

把一个长为n(n<=105)的数划成若干段，使得划分出的数最大值和最小值的差尽量的小。（新数不能有前导 0）

解题思路

首先，要使最大差值尽可能小，脑袋一拍想到：如果把这个数每一位都划一段，不是最大值能控制在9以内了？
有了这个性质，再往里思考，因为最大是9，再脑袋一拍，就能想到划分只有两种情况：每段长度相等，或者长度最大差1。

对于每段长度相等的情况，我们只需要枚举长度n的每个因数，分别从前到后求出最大差，取min即可。
对于长度差1的情况，答案若要小于9，只可能是出现了99…9x和100…0y这样的划分，其中x=2...9中的数字, y=0...7中的数字。

注意：如果位数是1和2，那么 99…9x 这个构型起始并不是9开始的，而是单个x，需要特判。
99...9x可能需要拆成若干个，所以应该找更长的100…0y类型。

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[200010],b[200010],c[200010];
char s[200010];
void minu(int *x,int *y,int n)
{
	int i;
	for(i=n;i>=1;i--) x[i]-=y[i];
	for(i=n;i>=1;i--)
		if(x[i]<0) x[i-1]--,x[i]+=10;
}
bool cmp(int *x,int *y,int n)
{
 	for(int i=1;i<=n;i++)
 		if(x[i]!=y[i]) return x[i]<y[i];
 	return 0;
}
int md(int n,int l)
{
	if(!a[1] && l>1) return 9;
	int *m1=a,*m2=a,i;
    for(i=0;i<n;i+=l)
	{
        if(!a[i+1] && l>1) return 9;
        if(cmp(a+i,m1,l)) m1=a+i;
        if(cmp(m2,a+i,l)) m2=a+i;
    }
    memcpy(b,m2,sizeof(int)*(l+10));
    minu(b,m1,l);
    for(i=1;i<l;i++)
		if(b[i]) return 9;
    return b[l];
}
int zz(int n,int l)
{
	int x=1,t0=0,t9=9;
    while(x<=n)
	{
        if(a[x]==1)
		{
            if(x+l>n || c[x+l-1]-c[x]) return 9;
            t0=max(t0,a[x+l]),x+=l+1;
        }
        else
		{
            if(x+l-1>n || c[x+l-2]-c[x-1]!=9*(l-1)) return 9;
	        t9=min(t9,a[x+l-1]),x+=l;
		}
    }
    return t0-t9+10;
}
int main()
{
	int t,n,ans,tot,i;
	scanf("%d",&t);
	while(t--)
	{
		ans=9;
		scanf("%d",&n);
		scanf("%s",s);
		for(i=1;i<=n;i++) a[i]=s[i-1]-'0';
		for(i=1;i<=n;i++)
			c[i]=c[i-1]+a[i];
		for(i=1;i<=n/2;i++)
		{
		    tot=zz(n,i);
		    ans=min(ans,tot);
		    if(n%i==0)
		    {
		    	tot=md(n,i);
		    	ans=min(ans,tot);
			}
		}
		printf("%d\n",ans);
	}
    return 0;
}