【題解】CSES - Permutations

題目連結

題目大意

請你構造一個長度為 $n$ 的 permutation 使得相鄰兩個數字的差 $> 1$，或輸出無解。

• $1 \leq n \leq 10^6$

題解

觀察到如果 $n = 2$ 或是 $n = 3$ 時無解。其他情況我們都可以構造出一組解，構造方法如下：

1. 由小到大放入 $1 \sim n$ 中的偶數
2. 由小到大放入 $1 \sim n$ 中的奇數

當 $n = 4$ 時，構造出 $[2, 4, 1, 3]$ 為合法的一組解。

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	if(n == 2 || n == 3) {
		cout << "NO SOLUTION\n";
	} else {
		vector<int> ans;
		ans.reserve(n);
		for(int i = 2; i <= n; i += 2) {
			ans.push_back(i);
		}
		for(int i = 1; i <= n; i += 2) {
			ans.push_back(i);
		}
		for(auto x : ans) {
			cout << x << " \n"[x == ans.back()];
		}
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】CSES - Permutations