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;
}