Wannafly挑战赛3 C.位数差【思维+离散化+二分+树状数组】

题目描述

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

输入描述:

第一行读入一个正整数 n (1 <= n <= 105)。

第二行读入 n 个非负整数，第 i 个表示a[i] (0 <= a[i] <= 108)。

输出描述:

一行表示答案。

示例1

输入

10
0 1 2 3 4 5 6 7 8 9

输出

20

思路：

考虑降低常数就行了。

问题很简单，我们只要考虑每个数后边有多少比他大的数而且能够进位即可，观察到数据范围，我们只要将10-a【i】，100-a【i】，1000-a【i】.....................依次进行计算，得到a【i】进位需要的最小的数值，然后树状数组随便搞搞就行了。

问题不难，一开始将太多数离散化导致了超时TAT。。。

Ac代码：

#include<bits/stdc++.h>
using namespace std;
/***********************************/
int n;
int tree[1000800];
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
void add(int x,int c)
{
    while(x<=n)
    {
        tree[x]+=c;
        x+=lowbit(x);
    }
}
/***********************************/
struct node
{
    int val,pos;
}a[100050],b[100050];
int pos[100050];
int cmp(node a,node b)
{
    return a.val<b.val;
}
int cmp2(node a,node b)
{
    return a.pos<b.pos;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].val);
            a[i].pos=i;
            b[i].val=a[i].val;
            b[i].pos=i;
        }
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++)pos[a[i].pos]=i;
        sort(a+1,a+1+n,cmp2);
        sort(b+1,b+1+n,cmp);
        memset(tree,0,sizeof(tree));
        long long int ans=0;
        for(int i=n;i>=1;i--)
        {
            int Temp=1;
            for(int j=1;j<=9;j++)
            {
                Temp*=10;
                if(Temp<=a[i].val)continue;
                else
                {
                    int p=-1;
                    int l=1;
                    int r=n;
                    int flag=0;
                    while(r-l>=0)
                    {
                        int mid=(l+r)/2;
                        if(b[mid].val>=Temp-a[i].val)
                        {
                            r=mid-1;
                            p=mid;
                        }
                        else l=mid+1;
                    }
                    if(p==-1)continue;
                    ans+=(sum(n)-sum(pos[b[p].pos]-1));
                }
            }
            add(pos[i],1);
        }
        printf("%lld\n",ans);
    }
}