2020牛客暑期多校训练营（第四场）D- Dividing Strings

传送门

Description

With powerful decision-making skills, ZYB can solve complex problems

ZYB has a decimal string {s}s of length {n}n. He wants to split the string into several (at least 2) non-empty continuous substrings and minimize the difference between the maximum value and the minimum value of the gifts. The value of a continuous substring is the value of it when it’s considered as a decimal number.
For instance, when the string ‘1230’ is split into ‘12’ and ‘30’, the values of the two parts are 12 and 30 separately. Notice that the substrings are not allowed to contain leading zero(s). For example, the only feasible way of splitting ‘001’ is ‘0’, ‘0’ and ‘1’.

Can you help ZYB find the fairest splitting?

简洁题意

• 把一个数字串划成若干段（至少两段），使得最大值和最小值的差尽量的小。注意不能有前导0

一个显然而重要的性质

• $ans\leq 9$ans≤9,因为把字符串分成单个数字后数字$x$x必为$0\leq x\leq 9$0≤x≤9

优化

Case 1

• 划成的每一段长度相等
• 因为$N$N 只有$10^5$105，我们可以枚举$N$N 的所有约数。对于给定约数，线性扫一遍判断答案、复杂度$O(N√N)$O(N√N)（而且跑不到）

---

Case 2

• 划成的段里最大段和最小段的长度差为1
• 答案若要小于$9$9，形式只可能是$99…9x$99…9x 和$100…0y$100…0y，其中$x=2..9$x=2..9, $y=0..7$y=0..7,因为$x$x不能是$1$1，$y$y 不能是$9$9(否则答案一定大于等于$9$9)
• 注意$9..99$9..99长度不好判断，所以我们只要找$10...0$10...0就可以了
• 复杂度$O(N)$O(N)

实现

#include<bits/stdc++.h>
using namespace std;
void sub(int* a,int *b,int n){//长度为n的数组a-b的结果 
    for(int i=n;i;i--)a[i]-=b[i];
    for(int i=n;i;i--)if(a[i]<0)a[i-1]--,a[i]+=10;
}
bool cmp(int* a,int* b,int n){//比较长度为n的数组a与b的大小 
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i])
            return a[i]<b[i];
    }
    return 0;
}
const int N=2e5;
int a[N],b[N];
int pre[N];
int solve_f(int len,int n){
    if(len>1&&!a[1])return 9;
    int* mi=a,*mx=a;
    for(int i=0;i<n;i+=len){
        if(len>1&&!a[i+1])return 9;
        if(cmp(a+i,mi,len))mi=a+i;//更新最小值 
        if(cmp(mx,a+i,len))mx=a+i;//更新最大值 
    }
    memcpy(b,mx,sizeof(int)*(len+10));//拷贝，可以用for替代 
    sub(b,mi,len);//最大减最小 
    for(int i=1;i<len;i++){
        if(b[i])return 9;
    }
    return b[len];
}
int solve_d(int len,int n){
    int p=1;
    int zero=0,nine=9;
    while(p<=n){
        if(a[p]==1){ 
            //len+1
            //10000000
            if(p+len>n||pre[p+len-1]-pre[p])//长度判断，0串判断 
                return 9;
            zero=max(zero,a[p+len]);//10000的末尾 
            p+=len+1;
        }
        else {
            //  len
            if(p+len-1>n||pre[p+len-2]-pre[p-1]!=9*(len-1))//长度判断，9串判断 
                return 9;
            nine=min(nine,a[p+len-1]);//9999的末尾 
            p+=len;
        }
    }
    return 10-nine+zero;
}
char s[N];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int ans=9,n;
        scanf("%d",&n);
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)a[i]=s[i]-'0';
        for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];//前缀和
        for(int i=1;i<=n/2;i++){
            int t=solve_d(i,n);
            ans=min(ans,t);
            if(n%i==0){
                int t=solve_f(i,n);
                ans=min(ans,t);
            }
        }
        cout<<ans<<'\n';
    }
}