信息奥赛题解｜LR SORT

浙理工2023新生赛｜LR SORT

---

🚀 题目浏览

【题目描述】

定义 LR SORT 为对一个大小为 $n$ 的数组 $a$ 进行 LR SORT 时，从 1 到 $n$ 遍历 $a_i$，每当 $i$ 为奇数时，将 $a_i$ 移动至数组 $b$ 的最左侧，当 $i$ 为偶数时，将 $a_i$ 移动至数组 $b$ 的最右侧，数组 $b$ 初始为空，代表排序后的数组。

如对于数组 $a=[3,1,4,5,2]$，数组 $b$ 在排序过程中依次序为 $[3]$ , $[3,1]$ , $[4,3,1]$, $[4,3,1,5]$, $[2,4,3,1,5]$ 。

请构造一个大小为 $n$ 的排列 $p$ ，使得经过 LR SORT 后其严格上升，即不存在 $i$ 满足 $p_i \geq p_{i+1}$ 。

一个大小为 $n$ 的排列指的是一个数组的大小为 $n$ 且元素 $1 \sim n$ 都恰好出现一次。

【输入】

输入第一行包含一个正整数 $T$ $(1 \leq T \leq 10^3)$，代表测试组数。

随后 $T$ 行，每行包含一个正整数 $n$ $(1 \leq n \leq 10^5)$。

确保 $\sum n \leq 2 \times 10^5$。

【输出】

输出 $T$ 行，每行包含一个大小为对应测试点 $n$ 的排列。

【输入样例】

2
1
3

【输出样例】

1 
2 3 1 

【原题链接】

https://acm.zstu.edu.cn/problem.php?id=4872

---

☘️ 题解分析

---

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;

void solve() {
    cin >> n;
    int i = (n + 1) / 2, j = i + 1;
    for (int k = 1; k <= n; k++) {
        if (k & 1) {
            cout << i << " ";
            i--;
        } else {
            cout << j << " ";
            j++;
        }
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}