CF1728C Digital Logarithm 题解

题目链接：CF1728C Digital Logarithm

题意：

我们定义 $f(x)$ 表示取出 $x$ 在十进制下的位数。( 如 $f(114514) = 6, \; f(998244353) = 9$ )。形式化讲，就是 $f(x) = \lfloor \log_{10} x \rfloor$

给定两个数组 $a$ 和 $b$，求执行若干次以下操作后使得 $a$ 和 $b$ 排序后相等的最小操作次数。

操作方法如下：

• 选择一个下标 $i$，将 $a_i$ 赋值为 $f(a_i)$ 或者将 $b_i$ 赋值为 $f(b_i)$。

输入格式：

第一行一个整数 $T \; (1 \le T \le 10^4)$ 表示测试样例组数。

对于每组测试样例，第一行为一个整数 $n \; (1 \le n \le 2 \cdot 10^5)$ 表示数组长度。

接下来的两行分别有 $n$ 个整数，表示数组 $a$ 和 $b \; (1 \le a_i,b_i < 10^9)$。

数据保证 $\sum n \le 2 \times 10^5$

输出格式：

对于每组测试样例，输出包含一行一个整数，表示最小操作次数。

记录一下这道在最后几秒交上去Accepted了然后又被Hacked的题。

可以发现这个数据范围下，再大的数至多两次就削成 $1$ 了。

根据贪心的思想，我们每次取出当前 $a$ 数组和 $b$ 数组各自的最大值

如果他们相同，就把他们同时扔掉。否则把较大的那个削一下。

说实话这东西看上去很对很简单，但是我就是没想到。。

然后我当时搞得可能常数太大了寄了。因为排序了好几遍。

时间复杂度 $O(2\sum n\log\sum n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)())

int n;
priority_queue<int> a,b;
int f(int x){return to_string(x).size();}
void clear()
{
    while(!a.empty()) a.pop();
    while(!b.empty()) b.pop();
}
void solve()
{
    clear(); cin >> n;
    for(int i=1,x; i<=n; i++) cin >> x, a.push(x);
    for(int i=1,x; i<=n; i++) cin >> x, b.push(x);
    int ans=0;
    while(!a.empty())
    {
        int x=a.top(), y=b.top();
        if(x > y)
        {
            a.pop(); a.push(f(x)); ++ans;
        }else if(x < y)
        {
            b.pop(); b.push(f(y)); ++ans;
        }else a.pop(),b.pop();
    }
    cout << ans << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q=1; cin >> _Q;
    while(_Q--)solve();
    return 0;
}