526互联

Codeforces Round 874 (Div. 3) B. Restore the Weather

发布时间 2023-09-05 21:22:53作者: zsxuan

给一个长为 \(n\) 的数组 \(a\) ，给一个长为 \(n\) 的乱序数组 \(b\) ，给一个正整数 \(k\) 。要求重排 \(b\) 使得 \(\forall i, |a_i - b_i| \leq k\) 。输出其中一种 \(b\) 的排列方式。

一个性质题。（div2 前几题很喜欢有序数组的经典性质）

总结一下有序数组的经典性质：（都容易证明）

  • 有序数组的差分数组最大值最小
    • 例题：Codeforces Round 894 (Div. 3) G
  • 给长为 \(n\) 的升序序数组加上 \({n, n - 1, n - 2, \cdots, 1}\) ，它的差分数组整体减一。
    • 例题：Codeforces Round 894 (Div. 3) G
  • 两个长为 \(n\) 的同有序数组可以使 \(\sum_{i = 1}^{n} a_i \cdot b_i\) 最大；两个长为 \(n\) 的逆有序数组可以使 \(\sum_{i = 1}^{n} a_i \cdot b_i\) 最小。
    • 例题：（Codeforces Round 892 (Div. 2) C. Another Permutation Problem）
  • 两个长为 \(n\) 的同有序数组可以使 \(c, (c_i = |a_i - b_i|)\) 的最大值最小；两个长为 \(n\) 的逆有序数组可以使 \(c, (c_i = |a_i - b_i|)\) 的最小值最大。
    • 例题：Codeforces Round 874 (Div. 3) B. Restore the Weather

另一个典的转化，\(\forall i, |a_i - b_i| \leq k\) ，即 \(|a_i - b_i|_{max} \leq k\) 。

于是将 \(a\) 按 \(\{a_i, i\}\) 排序，\(b_i\) 同序排序。则使得 \(c,(c_i = |a_i - b_i|)\) 的最大值最小。 \(ans_{a_i.second} = c_i\) 。

因为题目保证有解，否则可以讨论若 \(c_{max} > k\) ，则无解。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
	int n, k; std::cin >> n >> k;
	std::vector<std::pair<int, int> > a(n+1);
	std::vector<int> b(n+1);
	for (int i = 1, x; i <= n; i++) std::cin >> x, a[i] = {x, 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());
	std::vector<int> ans(n+1);
	for (int i = 1; i <= n; i++) ans[a[i].second] = b[i];
	for (int i = 1; i <= n; i++) std::cout << ans[i] << " \n"[i==n];
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}