双向链表

难题链接

 

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

 

 

题意: 有一个长为 n 的数列a[1]~a[n],以后对那一个数列实行删减操作,倘若 a[i]>a[i+1] 则删去 a[i] 和 a[i+1],举行完一轮过后固然还会有不满足的数,则开展第1轮删除操作,求最终剩下的数的个数,而且输出那个数?

思路: 使用双向链表举行模拟,对于每二个节点记录其左手的节点和左臂节点的下标,首先把1~n的下标都归入队列中,每一次从队列中抽出多个下标now , pre=a[now].l , next=a[now].r , 判断a[now].x<=a[next].x , 倘诺满意则象征合理,从队列中取下叁个数;不然将 pre 放入队列,因为明天要效仿删除 now 和 next ,删除之后恐怕pre和下一个节点大小关系就不客观了,所以要求放入队列中,别的还要开展

         a[pre].r=a[next].r;
         a[a[next].r].l=pre;
         a[next].l=pre;

    前多少个很醒目表示删除now和next,最终一个a[next].l=pre,是因为恐怕next也在队列中,下三个要判定是还是不是删除 next 和 a[next].r , 删除之后都供给将链表前后连接起来,举例对于n=5 , 2 5 3 1 4如此的数码,删除5和3数值后(对应的下表为2和3,下标从1从头),下三个3和1也不满意。

 

代码如下:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e5+5;
struct Node
{
    int l,r;
    int x;
}a[N];
queue<int>Q;

int main()
{
    int T; cin>>T;
    while(T--)
    {
        int n; scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].x);
            a[i].l=i-1;
            a[i].r=i+1;
            Q.push(i);
        }
        a[0].r=1; a[n+1].x=9999999;
        while(!Q.empty())
        {
            int now=Q.front(); Q.pop();
            int pre=a[now].l;
            int next=a[now].r;
            if(a[now].x>a[next].x)
            {
                Q.push(pre);
                a[pre].r=a[next].r;
                a[a[next].r].l=pre;
                a[next].l=pre;
            }
        }
        int ans=0;
        int now=a[0].r;
        while(now<=n)
        {
            ans++;
            now=a[now].r;
        }
        printf("%dn",ans);
        now=a[0].r;
        while(now<=n)
        {
            printf("%d ",a[now].x);
            now=a[now].r;
        }
        puts("");
    }
    return 0;
}

 

本文由华夏彩票发布于关于计算机,转载请注明出处:双向链表

您可能还会对下面的文章感兴趣: