under 题解 AT2648

---

题目要求我们多次翻转序列，但时间复杂度显然不允许。

思考发现可以在序列首尾插入来避免翻转操作。

可以借助 STL 容器。但是该选择哪一种容器呢？

---

以下内容部分引用自 cppreference

STL 中提供了三种支持首尾插入的容器。

std::vector

• 随机访问——常数 O(1)
• 在末尾插入或移除元素——均摊常数 O(1)
• 插入或移除元素——与到 vector 结尾的距离成线性 O(n)

std::deque

• 随机访问——常数 O(1)
• 在结尾或起始插入或移除元素——常数 O(1)
• 插入或移除元素——线性 O(n)

std::list

cppreference 并没有标注复杂度

list 通常实现为双向链表，因此具有类似链表的复杂度（和更大的常数）。

从实际运行来看，list 具有 O(1) 的随机插入 / 移除复杂度，但只有 O(N) 的随机访问。 不就是不能随机访问吗说那么多干啥

附性能测试实验一组

---

回到本题。题目需要从序列首尾插入，但不需要随机访问，因此 deque 和 list 都可以选择。为了避免常数影响，我们选择较快的 deque。

代码 (C++11) （卡到了最优解第一珂海星）

#include<algorithm>
#include<deque>
#include<iostream>

using namespace std;

int N, a;
deque<int> q;

int main() {
  cin >> N;
  
  for(int i = 1; i <= N; ++i) {
    cin >> a;
    if(i & 1) q.push_back(a);
    else q.push_front(a);
  }
  
  if(N & 1) reverse(q.begin(), q.end());
    // 序列长度是奇数时最后别忘了翻转
  for(auto it = q.begin(); it != q.end(); ++it)
    cout << *it << ' ';
  cout << '\n';
  
  return 0;
}

我永远喜欢 STL