【练习】位数差

位数差

https://ac.nowcoder.com/acm/problem/14380

题目

题目描述：

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

，0的位数为1。

输入描述：

第一行读入一个正整数 n (1 <= n <= 10⁵)。第二行读入 n 个非负整数，第 i 个表示a[i] (0 <= a[i] <= 10⁸)。

输出描述：

一行表示答案。

解析

1）知识点

这道题包含了分支递归和二分思想。

2）看题目

首先我们理解题目的话，就是要求出一个两层循环就散公式呗，平方复杂度可以算，但是会超时（代码放下面了）。

3）算法分析

但是这个问题很大，我们就想要把他变成很多小问题来解决。所以我们自然就会想到dp和分治递归。
这道题我们一个大问题我们就对半分成两个小问题来写，问题之间互不相干，我们也自然而然的分治递归。
递归的话，大问题怎么划分成小问题呢？
我们假设有一个问题ans，分成左右两个小问题 l，r （我们下面用calc表示递归函数）：就可以得到ans = calc(l) + calc(r) + h(l, r)。
（这里的h(l, r)就是两个区块之间关联的计算过程）
也就是说，我们现在就按照这个思路递归就可以得出答案了。

4）算法操作

既然我们都已经有思路了，我们现在最重要的就是求出
h(l, r)了。
calc(l) 和 calc(r) 都不重要，因为递归自己会求：
```
ll ans = calc(l, mid) + calc(mid + 1, r);
//h(l, r)下面会求
```
这里注意一下，我们的递归终点，就是左界 == 右界的情况：
```
if (l == r) return 0;
```
然后呢，我们的h(l, r)怎么求？
这里我就直接举例说明：h(a, b)我们已知一个确定的b = 12345。这说明如果答案要+1的a，一定会比1e6 - b要大。
这里你大概就能懂了：也就是说，如果大于1e6 - a的数据全都可以+1。同理可得，1e7 - b的数全都可以+2。

这就有一个好办法可以节省时间的做后面的步骤了：二分对答案进行查找。判断比10ⁿ - b大的a，有多少个，就统计下来就是答案：

int cmp[9] = { 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
for (int i = l; i <= mid; i++)
    for (int j = 0; j < 9; j++)
        if (cmp[j] - info[i] > 0) {
            auto en = info + r + 1;
            auto pos = lower_bound(info + mid + 1, info + r + 1, cmp[j] - info[i]);
            ans += en - pos;
        }

5）打代码

首先保存我们的数据。
然后就按我说的分治递归就好了。
下面全代码~

TLE代码

#include <iostream>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
int info[MAX];
//全局变量区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> info[i];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            int x = info[i] + info[j], y = info[i];
            string s1 = to_string(x), s2 = to_string(y);
            ans += s1.length() - s2.length();
        }
    cout << ans << endl;
    return 0;
}
//函数区

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
int cmp[9] = { 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
int info[MAX];
//全局变量区

ll calc(int l, int r);
//函数预定义区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> info[i];
    cout << calc(1, n) << endl;
    return 0;
}
ll calc(int l, int r) {
    if (l == r) return 0;
    int mid = l + r >> 1;
    ll ans = calc(l, mid) + calc(mid + 1, r);
    sort(info + mid + 1, info + r + 1);
    for (int i = l; i <= mid; i++)
        for (int j = 0; j < 9; j++)
            if (cmp[j] - info[i] > 0) {
                auto en = info + r + 1;
                auto pos = lower_bound(info + mid + 1, info + r + 1, cmp[j] - info[i]);
                ans += en - pos;
            }
    return ans;
}
//函数区

牛客算法竞赛入门课题解文章被收录于专栏

憨憨的专栏