Wannafly挑战赛3-C-位数差（二分）

题解：

         

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 1000005
ll a[maxn];
ll bit(ll x)
{
	if(x==0)
		return 1;
	ll cnt=0;
	while(x)
		cnt++,x/=10;
	return cnt;
}
bool comp(ll a,ll b)
{
	return a>b;
}
int main(void)
{
	int n;
	ll ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		ans-=(n-i)*bit(a[i]);
	}
	sort(a+1,a+n+1,comp);
	for(int i=1;i<=n-1;i++)
	{
		int l=i+1,r=n;
		ll now=bit(a[i]);
		while(l<=r)
		{
			int mid=(l+r)/2;
			if(bit(a[i]+a[mid])>now)
				l=mid+1;
			else
				r=mid-1;
		}
		ans+=(r-i)*(now+1)+(n-r)*now;
	}
	printf("%lld\n",ans);
	return 0;
}