ACM模版

描述

题解

这个题真心不难，典型的链表题，在 51Nod 上见过好多次同类型的题，可是我竟然无限 TLE ……至今未找到 bug ，在网上找了一份 AC 代码，发现他的方法比我的还要多很多操作，感觉比我的还慢啊，可是人家竟然 AC 了……很诧异啊……算了，两个代码都贴一下吧，希望大佬们可以看出我的 TLE 的尿点……

代码

One：

// TLE
#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 1e5 + 10;

int N;
int A[MAXN];
int pre[MAXN];
int net[MAXN];
int tmp[MAXN];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

template <class T>
inline void print_d(T x)
{
    if (x > 9)
    {
        print_d(x / 10);
    }
    putchar(x % 10 + '0');
}

void init(int cnt)
{
    // 构造链表结构
    for (int i = 1; i <= cnt; ++i)
    {
        pre[i] = i - 1;
        net[i] = i + 1;
    }
    net[cnt] = A[0] = 0;
}

void _erase(int x)
{
    int l = pre[x], r = net[x];
    if (l)
    {
        net[l] = r;
    }
    if (r)
    {
        pre[r] = l;
    }
}

int main(int argc, const char * argv[])
{
    int T;
    scan_d(T);

    while (T--)
    {
        scan_d(N);

        init(N);

        if (N == 0)
        {
            print_d(0);
            putchar(10);
            putchar(10);
            continue;
        }

        for (int i = 1; i <= N; i++)
        {
            scan_d(A[i]);
        }

        int x = 1, y = N;
        while (1)
        {
            int tot = 0, t = x;
            while (t)
            {
                if (t != x && A[t] < A[pre[t]])
                {
                    tmp[tot++] = t;
                }
                if (t != y && A[t] > A[net[t]])
                {
                    if (tmp[tot - 1] != t)
                    {
                        tmp[tot++] = t;
                    }
                }

                t = net[t];
            }

            for (int i = 0; i < tot; i++)
            {
                if (tmp[i] == x)
                {
                    x = net[tmp[i]];
                    pre[x] = 0;
                }
                if (tmp[i] == y)
                {
                    y = pre[tmp[i]];
                    net[y] = 0;
                }
                _erase(tmp[i]);
            }

            if (!tot)
            {
                break;
            }
        }

        int cnt = 0;
        for (int i = x; i; i = net[i])
        {
            cnt++;
        }

        print_d(cnt);
        putchar(10);
        if (cnt == 0)
        {
            putchar(10);
        }
        else
        {
            print_d(A[x]);
            for (int i = net[x]; i; i = net[i])
            {
                putchar(' ');
                print_d(A[i]);
            }
            putchar(10);
        }
    }

    return 0;
}

Two：

#include <iostream>
#include <cstring>
#include <vector>
#include <set>

#define PB push_back

using namespace std;

const int MAXN = 1e6 + 7;

int n, now, pre;
int A[MAXN];
int pe[MAXN];
int nt[MAXN];
int bz[MAXN];
set<int> si;
vector<int> vi;

int main(void)
{
    int T;
    cin >> T;

    while (T--)
    {
        memset(bz, 0, sizeof(bz));

        scanf("%d", &n);

        for (int i = 1; i <= n; i++)
        {
            scanf("%d", A + i);
            bz[i] = 0;
            pe[i] = i - 1;
            nt[i] = i + 1;
            si.insert(i);
        }
        nt[0] = 1, pe[n + 1] = n, pe[1] = 0, nt[n] = n + 1;
        A[0] = 0, A[n + 1] = MAXN;

        while (si.size())
        {
            vi.clear();
            for (auto &x : si)
            {
                int ntx = nt[x], pex = pe[x];
                if (A[pex] > A[x])
                {
                    vi.PB(pex);
                    vi.PB(x);
                }
                if (A[x] > A[ntx])
                {
                    vi.PB(x);
                    vi.PB(ntx);
                }
            }

            si.clear();
            for (auto &x : vi)
            {
                if (!bz[x])
                {
                    int ntx = nt[x], pex = pe[x];
                    nt[pex] = ntx, pe[ntx] = pex;
                    si.insert(pex);
                    bz[x] = 1;
                }
            }
        }

        int cnt = 0;
        for (int i = nt[0]; i != n + 1; i = nt[i])
        {
            cnt++;
        }
        printf("%d\n", cnt);

        for (int i = nt[0]; i != n + 1; i = nt[i])
        {
            printf("%d ", A[i]);
        }
        printf("\n");
    }

    return 0;
}