526互联

Educational Codeforces Round 117 (Rated for Div. 2) B. Special Permutation

发布时间 2023-09-16 04:23:24作者: zsxuan

给三个正整数数 \(n, a, b\) ，\(n\) 是偶数。写出 \(n\) 的任意一个排列满足左边一半的最小值等于 \(b\) 且右边一半的最大值等于 \(a\) 。

性质：

  • 控制某个区间的最小值，需要让这个区间的数尽可能大
  • 控制某个区间的最大值，需要让这个区间的数尽可能小

于是让排列左半的数尽可能大，右半的数尽可能小。

观察一：\(a \neq b\) 。

观察二：左边区间必须有 \(a\) ，且其他位置的数尽可能大；右边区间必须有 \(b\) ，且其他位置的数尽可能小。

  • 先排列，再通过 \(swap\) 定位 \(a, b\) 是不优的，会导致区间数尽可能大或尽可能小的性质失衡。
  • 排列的顺序没有意义。于是让 \(a, b\) 分别在第 \(1, n\) 位置 ，让剩余的数从大到小放入第 \(2 \sim n\) 位置。
  • 注意顺序枚举非 \(a, b\) 的数时要用 \(while\) 跳过而不是 \(if\) 。
view 
#include <bits/stdc++.h>
void solve() {
	int n, a, b; std::cin >> n >> a >> b;
	if (a == b) std::cout << -1 << '\n';
	else {
		std::vector<int> vec(n+1);
		vec[1] = a; vec[n] = b;
		for (int i = 2, cur = n; i < n; i++, --cur) {
			while (cur == a || cur == b) --cur;
			vec[i] = cur;
		}
		if (*std::min_element(vec.begin()+1,vec.begin()+n/2+1) == a && *std::max_element(vec.begin()+n/2+1,vec.end()) == b) {
			for (int i = 1; i <= n; i++) std::cout << vec[i] << " \n"[i==n];
		}
		else std::cout << -1 << '\n';
	}
}
signed main() {
    int _ = 1; std::cin >> _;
    while (_--) solve();
	return 0;
}