问题 L: Sock Sor

问题 L: Sock Sort
时间限制: 1 Sec 内存限制: 128 MB

题目描述
Today is a wonderful day. The sun is shining, the birds are chirping, and you have lots of interesting programming problems ahead of you. There’s just one thing bothering you: your socks aren’t matched!
Currently, you have 2n socks in an unmatched pile. n times, you will do the following:
● Take the top sock out of the pile of unmatched socks.
● Of the socks left in that pile, find the highest one that matches the sock you just took out and remove it from the pile.
● Put the matching pair of socks on the top of your pile of matched socks.
What will your matched pile look like once you’re done? You better hurry so you have time to get dressed for the programming contest!
Given your initial pile of unmatched socks, determine what the final pile of matched socks will look like.
输入
The first line will contain a single, positive integer, s, representing the number of scenarios. For each scenario, the first line will contain a single integer, n (1 ≤ n ≤ 105 ), representing the number of pairs of socks you own. The next line will contain 2n positive integers describing the style of each sock from top to bottom. These integers will be no greater than n, and there will be an even number of socks of each style.
输出
For each pile, output a single line containing 2n integers representing the matched pile of socks once you are done, in order of top to bottom.
样例输入 Copy
2
5
1 3 1 5 1 1 5 3 4 4
4
1 1 1 2 1 1 1 2
样例输出 Copy
4 4 1 1 5 5 3 3 1 1
1 1 2 2 1 1 1 1

第一次用的string的一些函数直接模拟的，虽然思路简单，但是却忽略了string函数本身的时间复杂度
第一次代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int main() {
    int T; scanf("%d", &T);while (T -- ){
    int n; scanf("%d", &n);string s;for (int i = 0; i < 2 * n; i ++ ) {
    int t; scanf("%d", &t);string c = to_string(t);s += c;}string str = "";while (s.size()) {
    string c = s.substr(0, 1);s.erase(0, 1);str = " " + c + " " + c + str;int t = s.find(c);s.erase(t, 1);}str.erase(0, 1);cout << str << endl;}return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;const int N = 1000010;int main(){
    int T; scanf("%d", &T);while (T -- ) {
    int n; scanf ("%d", &n);int a[N]; memset(a, 0, sizeof a);vector<int> v;for (int i = 0; i < 2 * n; i ++ ) {
    int x; scanf ("%d", &x);a[x] ++;if (a[x] & 1){
    v.push_back(x), v.push_back(x);}}reverse(v.begin(), v.end());for (auto it : v) printf("%d ", it);puts("");}return 0;
}