[Codeforces] CF1728C Digital Logarithm

题目传送门

很奇妙的一道题，我想到了正解，但是又没有完全想到

题意

我们定义 \(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

这是老师的思路，我没有写这个代码，但是明显这个思路比我的要简单的多

用两个优先队列存储两个序列，每次比较对头（即最大值），如果相等那么扔掉，否则操作较大的并添加到队尾，以此类推，直到序列为空

可以找时间谢谢这个代码，会比我的简单很多