[ABC254Ex] Multiply or Divide by 2 Solution

• [ABC254Ex] Multiply or Divide by 2 Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定大小为 $ n $ 的集合 $ A $ 和 $ B $，你可以对集合 $ A $ 中的元素 $ a_i $ 进行两种操作，分别为 $ a_i \leftarrow \lfloor \dfrac{a_i}{2} \rfloor $，和 $ a_i \leftarrow a_i \times 2 $。你需要操作集合 $ A $ 直至集合 $ A, B $ 完全相同。求最小操作次数，若无解输出 -1。

Solution

感觉这题的难度感觉完全不够 Ex，也完全不够紫，说这是 D 题我都信。。。

首先考虑转化两种操作，不难想到可以认为是在二进制中，前者即为右移一位，后者为左移一位。或者说前者是在二进制的末尾追加一个 $ 0 $，后者则是在二进制的末尾去掉一个数（可以为 $ 1 $ 也可以为 $ 0 $）。然后发现，这样的操作即缩小又放大没什么好性质，于是考虑转化。可以想到，对于将 $ A $ 集合中某个元素末尾追加一个 $ 0 $，可以转化为在 $ B $ 集合中某个元素末尾去掉一个 $ 0 $，同时注意这里去掉的只能为 $ 0 $.

综上我们题意转化为了，操作可以在 $ A $ 集合中去掉末尾一个属，也可以在 $ B $ 集合中去掉末尾一个 $ 0 $。于是想到维护两个优先队列，每次在两个集合中各取一个最大值，令其为 $ x, y $，若 $ x = y $，那么这两个数显然可以直接消除。若 $ x \gt y $，那么显然 $ x $ 会大于 $ y $ 中所有的数，而我们的操作又只能缩小一个数，不能增大，所以为了达到目标，一定需要对 $ x $ 进行一个缩小的操作，即 $ x \leftarrow \lfloor \dfrac{x}{2} \rfloor \(，于是进行这个操作，\) ans \leftarrow ans + 1 $，然后把剩下的值丢回优先队列。若 $ x \lt y $，我们显然也要将 $ y $ 缩小，而此时我们还有个限制，对 $ B $ 集合的操作只能去掉 $ 0 $，所以如果这个值最后一位为 $ 1 $ 那么显然无解，反之进行对应操作即可。

思路明显且代码实现极为简单。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template < typename T = int >
inline T read(void);

int N;
ll ans(0);
priority_queue < int, vector < int >, less < int > > a, b;

int main(){
    N = read();
    for(int i = 1; i <= N; ++i)a.push(read());
    for(int i = 1; i <= N; ++i)b.push(read());
    while(!a.empty() && !b.empty()){
        int x = a.top(), y = b.top(); a.pop(), b.pop();
        if(x > y)a.push(x >> 1), b.push(y), ++ans;
        else if(x < y){
            if(y & 1)printf("-1\n"), exit(0);
            else a.push(x), b.push(y >> 1), ++ans;
        }
    }printf("%lld\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_12_06 初稿