题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和两个长为$n$的数组$a$，$b$$(1 \leq a[i],b[i] \lt 10^9)$。

每次操作，把其中一个数组的一个元素替换成这个数的十进制长度。比如$123$替换成$3$。

若干次操作后，将$a$和$b$排序，要求所有$a[i]=b[i]$。

输出最小操作次数。

输入样例

4
1
1
1000
4
1 2 3 4
3 1 4 2
3
2 9 3
1 100 9
10
75019 709259 5 611271314 9024533 81871864 9 3 6 4865
9503 2 371245467 6 7 37376159 8 364036498 52295554 169

输出样例

2
0
2
18

算法

贪心

其实这个题的思路还是比较容易想的，由于所有元素都小于$10^9$，所以任何一个元素最多操作两次就会变成$1$。因此，借助哈希表$c_1$对$a$计数，哈希表$c_2$对$b$计数，这样我们就可以通过遍历其中一个哈希表，先把两个数组中原本就相同的元素剔除掉。

此时剩下的元素中，如果有大于等于$10$的数就肯定要被替换。再次借助哈希表，把$a$中所有大于等于$10$的元素替换一次存入哈希表$cc_1$，把$b$中所有大于等于$10$的元素也替换一次存入哈希表$cc_2$，小于$10$的元素原封不动地从$c_1$和$c_2$中搬过来，然后再次遍历一个哈希表去除它们两个的交集。

最后两个数组中剩余的元素只要还不是$1$，就得再替换一次变成$1$。

复杂度分析

时间复杂度

只进行了几次$O(n)$级别的遍历操作，时间复杂度应该是$O(n)$的，但被$codeforces$给卡哈希了，一直超时。换成有序表就过了，因此时间复杂度为$O(nlog_2n)$。

空间复杂度

开辟了几个哈希表来对元素计数，以及预处理出每个元素被替换一次之后的结果，最差情况下每个元素都作为$key$，对应一个$value$，因此这几个有序表都是$O(n)$级别的空间消耗。因此，算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;
const int N = 200010;
int n, a[N], b[N];

int get_len(int x) {
    int len = 0;
    while(x) {
        len++;
        x /= 10;
    }
    return len;
}

int solve() {
    map<int, int> c1, cc1, c2, cc2, num2len;
    for(int i = 1; i <= n; i++) {
        c1[a[i]]++;
        c2[b[i]]++;
        if(num2len.find(a[i]) == num2len.end()) num2len[a[i]] = get_len(a[i]);
        if(num2len.find(b[i]) == num2len.end()) num2len[b[i]] = get_len(b[i]);
    }
    for(int i = 1; i <= n; i++) {
        if(c2.find(a[i]) != c2.end()) {
            c1[a[i]]--;
            if(c1[a[i]] == 0) c1.erase(a[i]);
            c2[a[i]]--;
            if(c2[a[i]] == 0) c2.erase(a[i]);
        }
    }
    int ans = 0, m = 0;
    for(auto&[k, v]: c1) {
        if(k < 10) {
            cc1[k] += v;
            for(int j = 0; j < v; j++) a[++m] = k;
        }else {
            ans += v;
            cc1[num2len[k]] += v;
            for(int j = 0; j < v; j++) a[++m] = num2len[k];
        }
    }
    m = 0;
    for(auto&[k, v]: c2) {
        if(k < 10) {
            cc2[k] += v;
            for(int j = 0; j < v; j++) b[++m] = k;
        }else {
            cc2[num2len[k]] += v;
            ans += v;
            for(int j = 0; j < v; j++) b[++m] = num2len[k];
        }
    }
    for(int i = 1; i <= m; i++) {
        if(cc2.find(a[i]) != cc2.end()) {
            cc1[a[i]]--;
            if(cc1[a[i]] == 0) cc1.erase(a[i]);
            cc2[a[i]]--;
            if(cc2[a[i]] == 0) cc2.erase(a[i]);
        }
    }
    for(auto&[k, v]: cc1) {
        if(k > 1) ans += v;
    }
    for(auto&[k, v]: cc2) {
        if(k > 1) ans += v;
    }
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
        }
        printf("%d\n", solve());
    }
    return 0;
}

自定义哈希函数就可以在$O(n)$的时间复杂度下通过。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <chrono>

using namespace std;
const int N = 200010;
int n, a[N], b[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int get_len(int x) {
    int len = 0;
    while(x) {
        len++;
        x /= 10;
    }
    return len;
}

int solve() {
    unordered_map<int, int, custom_hash> c1, cc1, c2, cc2, num2len;
    for(int i = 1; i <= n; i++) {
        c1[a[i]]++;
        c2[b[i]]++;
        if(num2len.find(a[i]) == num2len.end()) num2len[a[i]] = get_len(a[i]);
        if(num2len.find(b[i]) == num2len.end()) num2len[b[i]] = get_len(b[i]);
    }
    for(int i = 1; i <= n; i++) {
        if(c2.find(a[i]) != c2.end()) {
            c1[a[i]]--;
            if(c1[a[i]] == 0) c1.erase(a[i]);
            c2[a[i]]--;
            if(c2[a[i]] == 0) c2.erase(a[i]);
        }
    }
    int ans = 0, m = 0;
    for(auto&[k, v]: c1) {
        if(k < 10) {
            cc1[k] += v;
            for(int j = 0; j < v; j++) a[++m] = k;
        }else {
            ans += v;
            cc1[num2len[k]] += v;
            for(int j = 0; j < v; j++) a[++m] = num2len[k];
        }
    }
    m = 0;
    for(auto&[k, v]: c2) {
        if(k < 10) {
            cc2[k] += v;
            for(int j = 0; j < v; j++) b[++m] = k;
        }else {
            cc2[num2len[k]] += v;
            ans += v;
            for(int j = 0; j < v; j++) b[++m] = num2len[k];
        }
    }
    for(int i = 1; i <= m; i++) {
        if(cc2.find(a[i]) != cc2.end()) {
            cc1[a[i]]--;
            if(cc1[a[i]] == 0) cc1.erase(a[i]);
            cc2[a[i]]--;
            if(cc2[a[i]] == 0) cc2.erase(a[i]);
        }
    }
    for(auto&[k, v]: cc1) {
        if(k > 1) ans += v;
    }
    for(auto&[k, v]: cc2) {
        if(k > 1) ans += v;
    }
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
        }
        printf("%d\n", solve());
    }
    return 0;
}