位数差

链接：https://ac.nowcoder.com/acm/problem/14380
来源：牛客网

题目描述

** 给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求 ，0的位数为1。 **

看到这道题，第一感觉数学问题；不过既然标签为二分，那就只能往二分靠；∑h(a,b)，分开写；
这里函数h(x)指的是x的位数；
n=2时，h(a1+a2)-h(a1);
n=3时，h(a1+a2)-h(a1),h(a1+a3)-h(a1),h(a2+a3)-h(a2)
以上可以看出，h(a1+a2)+h(a1+a3)+h(a2+a3)-(2*h(a1)+h(a2))；
拆开之后可以看出，ai+aj是每个数都相加一遍；a1+a2,a1+a3,...a1+an; a2+a3,a2+a4...a2+an；...
再看题目，暴力一定超时；而我们所需求的只是是ai+aj的位数，从题目中可以看出，位数最大为9；所以我们可以将数组排序（ai+aj与数组顺序无关，因为每个数都要相加一遍），对于一个数ai,枚举位数j从h(a[i])~h(a[i]+a[n])，在数组中二分查找值为k使a[i]+k的位数为j的最大位置；
看代码吧：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[120000],n;
ll h(ll x)//判断x的位数
{
    ll cnt=0,k=x;
    if(x==0) return 1;
    else{
    while(x)
    {
        cnt++;
        x/=10;
    }
    }
    return cnt;
}
int main()
{
    cin>>n;
    ll max1=0,ans=0,mmax=0;//max1为需要减去的部分的和，ans为a[i]+a[j]，mmax为数组最大值
    for(ll i=1;i<=n;i++) cin>>a[i],h(a[i]),mmax=max(mmax,a[i]),max1+=h(a[i])*(n-i);
    sort(a+1,a+1+n);
    for(int i=1;i<n;i++)//枚举从1~n-1
    {
        ll last=i;
        for(int j=h(a[i]);j<=h(a[i]+mmax);j++)//枚举位数j；例如，当j为1时，最大满足的位置为k，则last记为k；当j为2时，最大满足位置为h，则满足j为2的个数为（h-last）个
        {
            ll l=i+1,r=n;//因为，j>i，所以l从i+1开始
            while(l<r)
            {
                ll mid=(l+r)/2;
                if(h(a[mid]+a[i])>j) r=mid-1;
                else l=mid+1;
            }
            if(h(a[l]+a[i])>j) l-=1;
            ans+=(l-last)*j;//有l-last个数的位数为j
            last=l;
        }
    }
    cout<<ans-max1;
}