CF1255C O(nlogn)超时

C. League of Leesins

CF-1255C League of Leesins

题目大意：

一个长度为n的数列，可以将其每三个一组，拆成$n - 2$个数列.例如，数列$[1, 2, 3, 4, 5]$，可以将其拆成$[1, 2, 3],[2, 3, 4],[3, 4, 5]$这三个数列。下面给出拆过之后的，顺序打乱的$n - 2$个数列，让你找出原数列的情况.

输入

5
4 3 2
2 3 5
4 1 2

输出

1 4 2 3 5

样例说明

$n=5$有五个数，那么就有三个被拆分的数列，但它们的顺序都被打乱了。
还原为正常的顺序$[1, 4, 2],[4, 2, 3],[2, 3, 5]$，（情况不唯一，还可以反过来）则原序列为$[1,4,2,3,5]$。

TLE代码

//65388014  Nov/20/2019 00:32UTC+8  w616561153  1255C - League of Leesins   GNU C++11   Time limit exceeded on pretest 5    2000 ms     24000 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 50;
inline int read()
{
    int res = 0;
    char ch;
    ch = getchar();
    while(!isdigit(ch))
        ch = getchar();
    while(isdigit(ch)){
        res = res * 10 + ch - 48;
        ch = getchar();
    }
    return res;
}
struct Node
{
    int a, b, c;
    bool operator < (const Node &i) const{
        if(a == i.a){
            if(b == i.b)
                return c < i.c;
            return b < i.b;
        }
        return a < i.a;
    }
};
set<Node> st;
stack<int> s;
queue<int> q;
int vis[MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n - 2; i ++){
        int t1, t2, t3;
        t1 = read(), t2 = read(), t3 = read();
        st.insert(Node{t1, t2, t3});       //把三个数的全排列加入集合。因为无法保证按某一种顺序给出两个数，所以要把三个数可能出现的六种情况都加入集合中.
        st.insert(Node{t1, t3, t2});
        st.insert(Node{t2, t1, t3});
        st.insert(Node{t2, t3, t1});
        st.insert(Node{t3, t1, t2});
        st.insert(Node{t3, t2, t1});
        vis[t1] ++, vis[t2] ++, vis[t3] ++;   //记录每个数出现的次数，方便我们找到数列首尾元素.
    }
    int q1, q2, q3;
    for(int i = 1; i <= n; i ++){
        if(vis[i] == 1){
            q1 = i;
            break;
        }
    }
    Node node = *lower_bound(st.begin(), st.end(), Node{q1, 0, 0});
    if(vis[node.b] == 2){
        q2 = node.b, q3 = node.c;
    }
    else
        q2 = node.c, q3 = node.c;
    /*st.erase(Node{q1, q2, q3});
    st.erase(Node{q1, q3, q2});
    st.erase(Node{q2, q1, q3});
    st.erase(Node{q2, q3, q1});
    st.erase(Node{q3, q1, q2});
    st.erase(Node)*/
    q.push(q1), q.push(q2);
    for(int tt = 1; tt <= n - 2; tt ++){
        s.push(q.front());
        int f1, f2, f3;
        f1 = q.front(), q.pop();
        f2 = q.front();
        f3 = (*(lower_bound(st.begin(), st.end(), Node{f1, f2, 0}))).c;    //每次都是拿队列中的两个元素去找第三个元素。找到了这个数就是下一个元素.
     //因为每次找的时候第三个数都默认为0，所以不会出现涛哥说的那种找不到最后返回st.end()的情况.
        st.erase(Node{f1, f2, f3});
        st.erase(Node{f1, f3, f2});
        st.erase(Node{f2, f1, f3});
        st.erase(Node{f2, f3, f1});
        st.erase(Node{f3, f1, f2});
        st.erase(Node{f3, f2, f1});
        q.push(f3);
    }
    s.push(q.front());
    q.pop();
    s.push(q.front());
    q.pop();
    while(!s.empty()){
        printf("%d ", s.top());
        s.pop();
    }
    return 0;
}