题目链接:https://codeforc.es/contest/1728/problem/C

单独拿出来做一个博客,感觉我平时很少遇到的题。

大意就是,给出两个数组a和b,你可以对任意元素进行一个 log10(x)的操作,也就是说,你可以将这个数改变为它的位数。
最后求出最少通过多少次操作可以使得  a的某种排列 等于 b的某种排列。

贪心的看待这个问题,可以发现,最次我们可以通过两次操作使得  某一元素  变成 1。因为数据范围是1e9
这样,这个题要求最优解,我们需要做的就是解决比较大的数。因为小的数总是可以通过操作变成1或者使其更可能相等,因为数越小相等的可能性越大。
对于一个数的位数来讲。

如果a和b的大数不相同时,每次我们可以使得最大的那一个操作,然后再次对比。为什么要操作a b中最大数的最大的那个呢,因为这个数一定无法匹配了。这样每次操作我们都会改变这个数组顺序,所以这个题我们考虑用优先队列来维护。

附上出题人大佬的代码,这里很聪明的是使用了 to_string直接求出 一个数的位数。大佬不愧是大佬  ┭┮﹏┭┮%%%%

code:

#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n;
		scanf("%d", &n);
		vector<int> a(n), b(n);
		forn(i, n) scanf("%d", &a[i]); 
		priority_queue<int> qa(a.begin(), a.end());//建立堆,每次顶元素总是最大
		priority_queue<int> qb(b.begin(), b.end());
		int ans = 0;
		while (!qa.empty()){
			if (qa.top() == qb.top()){
				qa.pop();
				qb.pop();
				continue;
			}
			++ans;
			if (qa.top() > qb.top()){
				qa.push(to_string(qa.top()).size());
				qa.pop();
			}
			else{
				qb.push(to_string(qb.top()).size());
				qb.pop();
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}