首页 > > 程序设计 > C/C++ >

hdu 6215 -- Brute Force Sorting（双向链表+队…

2018-06-17 21:38:17来源：未知阅读 ()

题目链接

Problem Description

Beerus needs to sort an array of

Input

The first line of input contains an integer

Output

For eact test case output two lines.
The first line contains an integer

Sample Input

1 2 3 4 5

5 4 3 2 1

1 2 3 2 1

1 3 5 4 2

2 4 1 3 5

Sample Output

1 2 3 4 5

1 2

1 3

2 3 5

题意：有一个长为 n 的数列a[1]~a[n]，现在对这个数列进行删除操作，如果 a[i]>a[i+1] 则删去 a[i] 和 a[i+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("%d\n",ans);
        now=a[0].r;
        while(now<=n)
        {
            printf("%d ",a[now].x);
            now=a[now].r;
        }
        puts("");
    }
    return 0;
}