如何快速反转数字序列？C++代码优化求助（codebreaker.xyz 'smurf'题）

问题描述 #

我在解决codebreaker.xyz上名为'smurf'的题目，代码逻辑正确但运行效率太低，无法在输入规模s ≤ 200,000时1秒内完成。题目要求逐个输入一系列数字，每次输入后反转整个数组。例如：

输入：
6
0 1 2 1 2 0
输出：0 1 1 0 2 2

原代码（性能瓶颈版本） #

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define int unsigned int
vector<int> S;
int s, t;

int32_t main(){
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s;
    for(int i = 0; i < s; i++){
    cin >> t;
    S.push_back(t);
    reverse(S.begin(), S.end());
    }
    for(int j = 0; j < s; j++){
       cout << S[j] << " ";
    }
}   

性能瓶颈分析 #

原代码的核心问题是时间复杂度为O(n²)：每次向数组尾部添加元素后调用reverse，而reverse操作的时间复杂度是O(k)（k为当前数组长度）。当n=200,000时，总操作次数约为2×10¹⁰，远超1秒内能处理的运算量（约1×10⁸次），必然超时。

优化方案 #

不需要实际执行每次反转操作，通过观察操作规律直接构造最终数组：
每次插入元素后反转数组，等价于最终数组的元素顺序满足以下规则：

1. 先从最后一个输入元素开始，每隔一个元素取一个（逆序取偶数位置的元素，若输入规模为奇数则包含第一个元素）
2. 再从第一个或第二个元素开始，每隔一个元素取一个（正序取奇数位置的元素）

优化后的代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int s;
    cin >> s;
    vector<int> nums(s);
    for (int i = 0; i < s; ++i) {
        cin >> nums[i];
    }

    vector<int> res;
    // 第一部分：从末尾开始，步长-2取元素
    for (int i = s - 1; i >= 0; i -= 2) {
        res.push_back(nums[i]);
    }
    // 第二部分：根据s的奇偶决定起始位置，步长+2取元素
    int start = (s % 2 == 0) ? 0 : 1;
    for (int i = start; i < s; i += 2) {
        res.push_back(nums[i]);
    }

    // 输出结果
    for (size_t i = 0; i < res.size(); ++i) {
        if (i > 0) cout << " ";
        cout << res[i];
    }
    cout << endl;

    return 0;
}

优化效果 #

优化后的代码时间复杂度为O(n)，仅需两次线性遍历即可构造结果数组，完全能在1秒内处理s=200,000的输入规模。同时保留了ios_base::sync_with_stdio(false)等加速输入输出的操作，进一步提升运行效率。

内容的提问来源于stack exchange，提问作者Sahityan Vijay Anand Savitha