526互联

Technocup 2022 - Elimination Round 2 Two Arrays

发布时间 2023-09-26 17:21:32作者: zsxuan

给定两个数组 \(a_1, a_2, \cdots, a_n\) 和 \(b_1, b_2, \cdots, b_n\) 。

定义 \(a\) 的一次操作：

  • 选择任意一个非负整数 \(k(0 \leq k \leq n)\) 。
  • 选择任意 \(k\) 个独立的下标 \(i_1 \leq i_2 \leq \cdots \leq i_k \leq n\) 。
  • 对 \(a_{i_1}, a_{i_2}, \cdots, a_{i_k}\) 加 \(1\) 。
  • 以任意顺序重排 \(a\) 数组。

询问 \(a\) 能否经过严格一次操作后得到 \(b\) 。

不妨让 \(b\) 有序，则 \(a\) 经过操作后，可以得到有序的 \(b\) 对若干个位置 \(-1\) 。

对相同的 \(b_i, b_j\) ，让 \(-1\) 的操作尽可能往左，则得到的新数组 \(c\) 也有序。如果 \(a\) 可以得到 \(b\) ，则 \(c\) 可以为 \(a\) 。

于是对 \(a\) \(b\) 排序，若 \(0 \leq b_i - a_i \leq 1\) ，则 \(a\) 可以得到 \(b\) 。

view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::vector<int> a(n+1), b(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) std::cin >> b[i];
	std::sort(a.begin() + 1, a.end());
	std::sort(b.begin() + 1, b.end());
	int ok = 1;
	for (int i = 1; i <= n; i++) ok &= (b[i] - a[i] == 0 || b[i] - a[i] == 1);
	std::cout << (ok ? "YES" : "NO") << "\n";
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}