URL：https://codeforces.com/group/OcmZ7weh45/contest/487583/problem/J

目錄

Problem/題意

Thought/思路

Code/代碼

---

Problem/題意

給出一個長度為 N 的序列，其中的元素都是奇數。

現在要求在兩個奇數之間插入一個偶數，使得這三個數遞增或遞減。

一共需要插入 N - 1 個偶數，并且要求這 N?-?1 個偶數都不相同。

Thought/思路

顯然這道題的關鍵就在于，兩個奇數之間會有 >= 1 個偶數存在。

我們將兩個奇數視作一個區間（一共 N - 1 個區間，小的奇數作為左端點），那么我們在選擇了某個偶數 X 后，很可能就會占用了其他區間僅有的一個偶數 X，使得條件不滿足。

---

（貪心）我們可以嘗試先選擇一個區間中最小的偶數，然后在其之后的區間也同樣選擇區間中還沒有被選過的偶數中最小的哪個。

---

問題就轉換為，怎么保證每個區間選中的最小的偶數不會重復，這就要看我們是如何對這 N -?1 個區間排序的。

（1）如果我們按照左端點優先遞增來排序，就會出現左端點很小，右端點很大的情況，這意味著：明明這個區間可以選到一個很大的偶數，大到不會影響其他所有區間，而現在卻因為先選擇了可以選擇的最小偶數，導致占用了排在它之后的區間唯一可以選擇的偶數。

舉個例子：

[1, 3] => 2

[1, 5] => 4

[3, 100000] => 6

[5 7] => 選不了，錯誤

（2）因此我們再考慮按照右端點優先遞增來排序，顯然由于有著右端點的限制，假設右端點嚴格遞增，那么每個區間之間都一定能選到互異的偶數：比如 [1, 3]、[1, 5]、[1, 7] 選擇 2、4、6。

而就算前后兩個區間右端點相同，由于我們在前面的區間里已經選完了可以選擇的最小的偶數，因此后面這個區間肯定就是永遠無法選到互異的偶數的，比如：[1, 3]、[1, 7]、[3, 7]、[5, 7]。

綜上，我們選擇按照右端點優先遞增來排序。

---

核心思路就是上面這些，還有一個小問題：

查找最小偶數的時候需要使用二分，當我們選擇 set 保存所有的偶數時，二分時必須要使用 set 自帶的 upper_bound，而不能使用 algorithm 的 upper_bound。前者二分復雜度 O(logn)，后者二分復雜度 O(n)，很容易超時。

Code/代碼

#pragma GCC optimize(2)#include "bits/stdc++.h"struct node {int x, y, id;bool operator < (const node &t) const {if (y == t.y) return x < t.x;else return y < t.y;}
}p[200007];int a[200007];void solve() {int n; std::cin >> n;for (int i = 1; i <= n; ++ i) {std::cin >> a[i];if (i == 1) continue;int l = std::min(a[i], a[i - 1]), r = std::max(a[i], a[i - 1]);p[i - 1] = {l, r, i - 1};}std::sort(p + 1, p + n);std::set <int> st;for (int i = 2; i <= 2 * n - 2; i += 2) st.insert(i);bool flag = true;std::vector <int> ans(n);for (int i = 1; i <= n - 1; ++ i) {int l = p[i].x, r = p[i].y, id = p[i].id;//std::cout << "l=" << l << "  r=" << r << " ";auto even = st.upper_bound(l);if (*even < r) {//std::cout << "even=" << *even;ans[id] = *even;st.erase(even);} else {flag = false;}//std::cout << "\n";}if (flag) {for (int i = 1; i <= n - 1; ++ i) std::cout << ans[i] << " ";} else {std::cout << -1;}std::cout << "\n";
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(0); std::cout.tie(0);int t; std::cin >> t;while (t --) solve();return 0;
}