题解：CF2061D Kevin and Numbers

题意

有合并这个操作，当且仅当两数之差小于

1

时可以合并，问能否通过此操作将数组

a

转化成数组

b

。

解法

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

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

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

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

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

代码如下

CPP

#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";
	}
}

题解：CF2061D Kevin and Numbers

文章操作

题意

解法

相关推荐

评论

题解：CF2061D Kevin and Numbers