https://codeforces.com/contest/2061/problem/D
题目大意
给出 $n$ 长的数组 $a$ 和 $m$ 长的数组 $b$。满足 $1 \le m \le n \le 2 \times 10^5$ 和 $1 \le a_i, b_i \le 10^9$。
可以执行下述操作若干次：
从 $a$ 中选出 $x, y$ 满足 $|x - y| \le 1$。将其从 $a$ 中删掉，再将 $x + y$ 加入。
问是否可以将 $a$ 转化为 $b$。
简要题解
观察：
- 合并是不好操作的，但是某个 $b_i$ 如果是从 $a$ 中的数组合来的，那么头一次分拆的方式是唯一的。
- $b$ 中最大的数如果在 $a$ 中没有，则一定需要拆开变成多个 $a_i$ 的和。
- 变化不改变整个数组的和，所以如果 $sum(a) \neq sum(b)$，无解。
- $a_i$ 中剩余的最大值已经大于 $b_i$ 中剩余的值了，此时也是无解的。
有了这些思路就可以写代码了。用优先队列依次取出 $b_i$ 然后用 multiset 维护还可用的 $a_i$。但是注意到 $a_i, b_i$ 可以很大，如何保证复杂度呢？
一种方式是，如果 $b$ 的拆分超过了 $n - m$ 次，我们会得到多于 $n$ 个元素，这肯定是不行的，这样做的时间复杂度是 $(n + m) \log n$ 的。（注意如果不用观察 3，需要判断是否 $a$ 中元素也都用完。）
复杂度
$T$：$O((n + m) \log n)$
$S$：$O(n + m)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, m; cin >> n >> m;
vector<int> a(n), b(m);
for (int& i : a) cin >> i;
for (int& i : b) cin >> i;
priority_queue<int> se;
for (int i : a) se.push(i);
priority_queue<int> qu;
for (int i : b) qu.push(i);
while (!qu.empty()) {
int u = qu.top(); qu.pop();
if (se.top() > u) {
cout << "No\n";
return;
}
if (se.top() == u) {
se.pop();
continue;
}
if (m == n) {
cout << "NO\n";
return;
}
qu.push(u / 2);
qu.push((u + 1) / 2);
m++;
}
if (!se.empty()) {
cout << "NO\n";
} else {
cout << "Yes\n";
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
另一种方法
赛时写的是利用观察 3 和 4 来卡复杂度。
考虑对于合法情况，显然复杂度是一样的，仍然是拆了 $n - m$ 轮。
感觉上这个复杂度应该是没问题的，没想出怎么构造出那种特别差情况，但感觉也不是特别好证明。
对于非法情况 $sum$ 不等的直接 $O(n)$ 就检查掉了，那么只考虑 $sum$ 相同，但是中间某个时刻 $a_i$ 剩余最大值大于 $b'$ 最大值这种情况。考虑此时 $max(a') = x$ 已经有一些元素匹配了则这些元素 $\ge x$。此时所有 $\ge x$ 的 $b$ 的元素，要么已经匹配了，要么拆到了 $\ge \frac{x}{2}$ 的值。
void solve() {
int n, m; cin >> n >> m;
vector<int> a(n), b(m);
for (int& i : a) cin >> i;
for (int& i : b) cin >> i;
LL suma = 0, sumb = 0;
for (int i : a) suma += i;
for (int i : b) sumb += i;
if (suma != sumb) {
cout << "No\n";
return;
}
priority_queue<int> se;
for (int i : a) se.push(i);
priority_queue<int> qu;
for (int i : b) qu.push(i);
while (!qu.empty()) {
int u = qu.top(); qu.pop();
if (se.top() > u) {
cout << "No\n";
return;
}
if (se.top() == u) {
se.pop();
continue;
}
qu.push(u / 2);
qu.push((u + 1) / 2);
}
cout << "Yes\n";
}
Next: [CF] E. Kevin and And - IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)