题目链接: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; }