题解：CF2061D Kevin and Numbers

· · 题解

题意

有合并这个操作，当且仅当两数之差小于 1 时可以合并，问能否通过此操作将数组 a 转化成数组 b。

解法

很明显，这道题只有合并和拆分两种解法，由于答案数组不一定有序，所以我们可以用优先队列维护操作。

那现在就可以考虑合并和拆分两种方法：

  1. 合并：这是题目中的方法，也是我一开始想到的方法，通过小根堆维护最小值和次小值，当最小值与答案序列最小值相同时同时取出队列，否则合并最小和次小值加入队列。

    但是这样做有一个问题，本来 x 和 x + 1 存在， 可以合成在数组 b 中的 y，但是由于 x + 1不为最小值，数组 b 中也不存在 2x，就会导致答案错误。如果要处理这个问题，需要 dp 分类讨论，较麻烦，于是考虑拆分。

  2. 拆分：这是题目方法的逆运用，将 b 数组的数拆分，直到拆出 a 中的元素。

    这个方法解决合并不唯一的问题，由于一个元素要么为奇数要么为偶数，为了拆出两数之差小于 1 的组合，当奇数时只存在 x 与 x + 1，偶数时只存在 x 和 x。方案唯一，就不存在问题。

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
priority_queue <int> q;
priority_queue <int> p;
signed main(){
    int t;
    cin >> t;
    while(t--){
        while(!q.empty()) q.pop();
        while(!p.empty()) p.pop();
        int n,m;
        cin >> n >> m;
        while(n--) {int x;cin >> x;p.push(x);}
        while(m--) {int x;cin >> x;q.push(x);}
        while(!q.empty() && !p.empty()){
            while(p.top() == q.top() && !q.empty() && !p.empty()){
                q.pop();
                p.pop();
            }
            if(!(!q.empty() && !p.empty())) break;
            if(q.top() < p.top() || q.size() >= p.size()) break;
            int x = q.top(),a,b;
            a = x / 2,b = x - a;
            q.pop();
            q.push(a);
            q.push(b);
        }
        if(q.empty() && p.empty()) cout << "Yes\n";
        else cout << "No\n";
    }
}