題意 ：

• 對于一個長度為n的排列和一個空序列ans，每次取當前最左邊或者最右邊中最小的值，如果取的是最左邊，插入序列ans的最左邊，然后在排列中刪除這個數，如果取的是最右邊，插入最右邊，刪除
• 現在給出ans序列，問是否存在排列使得操作后的結果是ans，輸出任意方案

思路 ：

• 首先，最后插入的數字一定是排列中最大的數字，也就是它一定在ans的左/右
• 我們檢測ans的首尾是否有一個n，如果不存在一定無解
• 如果存在 ：
• 1.ans[1] == n，我們把ans[1]放到原數組的最左邊，由于它是最大的，在每一次的操作中，它都可以讓另一個數被取走，它本身最后才被取走，由于構造出來的結果是最外層的先被比較然后放入新的序列中，因此，將$[2,n]$逆序即可
• 2.ans[n] == n，對于$[1,n?1]$的數字，它們同樣是逆序存儲的
• reverse第二個參數是）而不是]的
• return cout << xxx << endl, void();，就不用換行return了

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> using namespace std;typedef long long ll; typedef pair<int, int> PII;#define endl '\n' #define fi first #define se second #define push_back #define rep(i, l, r) for (ll i = l; i <= r; i ++ )const int N = 2e5 + 10;int n, a[N];void solve() {cin >> n;for (int i = 1; i <= n; i ++ ) cin >> a[i];if (a[1] != n && a[n] != n) return cout << -1 << endl, void();if (a[1] == n) reverse(a + 2, a + n + 1);else if (a[n] == n) reverse(a + 1, a + n);for (int i = 1; i <= n; i ++ ) cout << a[i] << " \n"[i == n]; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; }

總結

以上是生活随笔為你收集整理的Polycarp Recovers the Permutation 构造（1000）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。