Brute Force Sorting 链表\模拟 [2017 ACM/ICPC Asia Regional Qingdao Online]

Brute Force Sorting题目链接

Problem Description

Beerus needs to sort an array of N integers. Algorithms are not Beerus’s strength. Destruction is what he excels. He can destroy all unsorted numbers in the array simultaneously. A number A[i] of the array is sorted if it satisfies the following requirements.
1. A[i] is the first element of the array, or it is no smaller than the left one A[i−1].
2. A[i] is the last element of the array, or it is no bigger than the right one A[i+1].
In [1,4,5,2,3], for instance, the element 5 and the element 2 would be destoryed by Beerus. The array would become [1,4,3]. If the new array were still unsorted, Beerus would do it again.
Help Beerus predict the final array.

Input

The first line of input contains an integer T (1≤T≤10) which is the total number of test cases.
For each test case, the first line provides the size of the inital array which would be positive and no bigger than 100000.
The second line describes the array with N positive integers A[1],A[2],⋯,A[N] where each integer A[i] satisfies 1≤A[i]≤100000.

Output

For eact test case output two lines.
The first line contains an integer M which is the size of the final array.
The second line contains M integers describing the final array.
If the final array is empty, M should be 0 and the second line should be an empty line.

Sample Input

5
5
1 2 3 4 5
5
5 4 3 2 1
5
1 2 3 2 1
5
1 3 5 4 2
5
2 4 1 3 5

Sample Output

5
1 2 3 4 5
0

2
1 2
2
1 3
3
2 3 5

Source
2017 ACM/ICPC Asia Regional Qingdao Online

首先想到的是暴力求解,但是发现暴力肯定TLE.然后观察一下就会发现,后面减去是根据前面减去的清空,这样记录一下前面减去的状态,然后根据前面的位置遍历,这样时间复杂度为O(n)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100005;

int T;
int n;
int a[N];
int pre[N];
int nex[N];
int vis[N];
set<int> ss;
vector<int> tmp;


void del(int cur)
{
    nex[ pre[cur] ] = nex[cur];
    pre[ nex[cur] ] = pre[cur];
    vis[cur] = 1;
    ss.insert(pre[cur]);
}


int t;
int main()
{
//    freopen("data.txt","r",stdin);

    scanf("%d", &T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        ss.clear();
        scanf("%d",&n);
        pre[0] = -1;
        nex[0] = 1;
        a[0] =-1;

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&t);
            a[i] = t;
            pre[i] = i-1;
            nex[i] = i+1;
        }

        a[n+1] = 1000005;
        nex[n+1] = -1;
        pre[n+1] = n;

        int cas = 1;
        for(int i=1;i<=n;i++)
        {
            ss.insert(i);
        }

        while(1)
        {
            tmp.clear();
            for(auto &it : ss)
            {

                if(vis[it]) continue;
                if(it!=0&&a[it]< a[pre[it]] || a[it]> a[nex[it]] )
                {
                    tmp.push_back(it);
                }

                if(nex[nex[it]] !=-1)
                {
                    if( a[ nex[it] ] <  a[it] || a[nex[it]]  > a[ nex[nex[it]] ] )
                    {
                        tmp.push_back(nex[it]);
                    }
                }
            }


            ss.clear();
            int tlen = tmp.size();
            for(int i=0; i<tlen ;i++)
            {
                if(vis[tmp[i]]) continue;
                del(tmp[i]);
            }

            if(tmp.size()==0)
            {
                break;
            }
        }

        int ans = 0;
        int cur = nex[0];
        while(cur!=-1)
        {
            if(cur!=0&&cur!=n+1)
                ans++;
            cur = nex[cur];
        }

        printf("%d\n",ans);

        cur = nex[0];
        while(cur!=-1)
        {
            if(cur!=0&&cur!=n+1)
                printf("%d ",a[cur]);
            cur = nex[cur];
        }
        printf("\n");
    }
    return 0;
}