AtCoder Beginner Contest 254 Ex. Multiply or Divide by 2（思维题/优先队列）

题目

初始有两个长为n(n<=1e5)的可重集合a和b，第i个数分别是ai,bi(0<=ai<=1e9,0<=bi=1e9)

你可以执行以下两种操作若干次：

1. 从A集合中选一个数x出来，令x变为2x后，再放回A集合

2. 从A集合中选一个数x出来，令x变为x/2向下取整后，再放回A集合

问让A和B两个集合完全相同的最小操作次数，如果不能实现输出-1

思路来源

AtCoder Beginner Contest 254 A-Ex - 知乎

题解

典中典问题

cf好像后来也出过一个，只是好像要输出具体方案，但是思路是一致的

如果A和B集合能完全相同，a和b一定存在一组一一映射关系，

不妨ai最后映射上的数是bj，且ai执行过第一种乘2操作，

那么，可以视为bj执行了一次除以2操作，前提是bj需要是偶数

将两种新操作改写为，

1. 从B集合中选一个偶数x出来，令x变为x/2，再放回B集合

2. 从A集合中选一个数x出来，令x变为x/2向下取整后，再放回A集合

这样两种操作就是对称的，并且数是只会变小的，所以就可以贪心地从最大数开始考虑了

使两个集合完全相同，等价于一对一对消去，能将两个集合消除空

记a集合中的最大数为mxa，b集合中的最大数为mxb

①若mxa=mxb，成对消除

②若mxb>mxa

（1）若mxb为奇数，不能操作，输出-1

（2）若mxb为偶数，mxb/2后放回，记一次操作

③若mxa>mxb，mxa/2后放回，记一次操作

代码

#include
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],cnt;
priority_queue<int>pa,pb;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        pa.push(a[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&b[i]);
        pb.push(b[i]);
    }
    while(!pa.empty()){
        if(pa.top()==pb.top()){
            pa.pop();pb.pop();
        }
        else if(pb.top()>pa.top()){
            if(pb.top()&1){
                puts("-1");
                return 0;
            }
            int x=pb.top();pb.pop();
            pb.push(x>>1);cnt++;
        }
        else if(pa.top()>pb.top()){
            int x=pa.top();pa.pop();
            pa.push(x>>1);cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}