很奇妙的一道题，我想到了正解，但是又没有完全想到
题意
我们定义 \(f(x)\) 表示取出 \(x\) 在十进制下的位数。( 如 \(f(114514) = 6, \; f(998244353) = 9\) )。形式化讲，就是 \(f(x) = \lfloor \log_{10} x \rfloor + 1\)。
给定两个数组 \(a\) 和 \(b\)，求执行若干次以下操作后使得 \(a\) 和 \(b\) 排序后相等的最小操作次数。
操作方法如下：
- 选择一个下标 \(i\)，将 \(a_i\) 赋值为 \(f(a_i)\) 或者将 \(b_i\) 赋值为 \(f(b_i)\)。
思路1
很明显，任何数操作两次，即\(f(f(x))\)，一定为\(1\)
所以，可以模拟这两种操作。
首先将两个序列去重，再把每个数都进行一次操作并记录，接着继续去重，然后剩下的就都要被变为1，也就是每个数都要被操作一次
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int a[Maxn],b[Maxn],n;
int ans;
bool cmp(int x,int y)
{
return x>y;
}
void init()
{
bool fa[Maxn]={},fb[Maxn]={};
int nowa,nowb;
priority_queue<int> qa,qb;
nowa=nowb=1;
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
for(;nowa<=n && nowb<=n;)
{
if(a[nowa]==b[nowb]) fa[nowa]=1,fb[nowb]=1,nowa++,nowb++;
else if(a[nowa]<b[nowb]) nowb++;
else nowa++;
}
for(int i=1;i<=n;i++)
{
if(!fa[i]) qa.push(a[i]);
if(!fb[i]) qb.push(b[i]);
}
int now=1;
while(!qa.empty() && !qb.empty())
{
a[now]=qa.top(),b[now]=qb.top();
now++;
qa.pop(),qb.pop();
}
n=now-1;
}
int f(int x)
{
int re=0;
while(x) re++,x/=10;
return re;
}
void print()
{
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
cout<<"size="<<n<<endl;
for(int i=1;i<=n;i++) printf("%2d ",a[i]);cout<<endl;
for(int i=1;i<=n;i++) printf("%2d ",b[i]);cout<<endl;
}
int run()
{
cin>>n;ans=0;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
init();
if(n==0)
{
cout<<0<<endl;
return 0;
}
for(int i=1;i<=n && a[i]>9;i++) ans+=(a[i]!=1),a[i]=f(a[i]);
for(int i=1;i<=n && b[i]>9;i++) ans+=(b[i]!=1),b[i]=f(b[i]);
// print();
init();
// print();
for(int i=1;i<=n;i++) ans+=(a[i]!=1),a[i]=f(a[i]);
for(int i=1;i<=n;i++) ans+=(b[i]!=1),b[i]=f(b[i]);
init();
// print();
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--) run();
}
其中，init是去重，就是把两个数组排序，并使用两个坐标记录两个序列的位置，那个较小那个向后移动，直到相等或变得比另一个更大。如果两个相等，那么就标记并删除
思路2
这是老师的思路，我没有写这个代码，但是明显这个思路比我的要简单的多
用两个优先队列存储两个序列，每次比较对头（即最大值），如果相等那么扔掉，否则操作较大的并添加到队尾，以此类推，直到序列为空
可以找时间谢谢这个代码，会比我的简单很多