洛谷 P1716 双调序列

题目描述

电脑组的童鞋们经常玩一些智力 PK 小游戏，某月某日，发源于小朋友又发明了一种新的序列：双调序列，所谓的双调呢主要是满足如下条件描述：

假定有 $n$（$n\le 1000$）个整数（都在 long int 范围内，即 $-2147483648\sim 2147483647$），双调序列的第一个数是 $n$ 个整数中的最大数，第二个数是 $n$ 个整数中的最小数，第三个数是 $n$ 个数中的第二大数，第四个数是 $n$ 个数中的第二小数……取过的数不能再取，依次类推，直到结束。

聪明的你听完描述就抿嘴笑了吧？那就请你用程序正确的帮他找出这 $n$ 个数的双调序列。

输入格式

第一行为一个整数 $n$。

接下来 $n$ 行给出了题目中所述的 $n$ 个整数，每行包含一个整数。

输出格式

有 $n$ 行，每行为一个整数，是满足条件的双调序列

样例 #1

样例输入 #1

5
10
-1
3
3
-9
1
2
3
4
5
6

样例输出 #1

10
-9
3
-1
3
1
2
3
4
5

提示

对于 $100\%$ 的数据，$1\le n\le 1000$。

分析：

这不就是把快速排序的结果分成两半，交叉输出吗？
我们在将所有数字都排好序后用一个循环，i从1枚举至n，每次先输出a[n+1-i]，再输出a[i]。

因为每个数的不小于-2147483648，所以每次输出完以后我们可以将输出的数从新赋值为一个小于-2147483648的数。在之后的输出前先判断一下，如果已经被赋值了，说明输出完了，退出循环。

代码：

#include

using namespace std;

long long n,a[10000];

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i]; 
    }

    sort(a+1,a+n+1);//快速排序

    for(int i=1;i<=n;i++)
    {
        if(a[n+1-i]==-2147483649)
        {
            break;
        }

        cout<<a[n+1-i]<<endl;

        a[n+1-i]=-2147483649;

        if(a[i]==-2147483649)
        {
            break;
        }

        cout<<a[i]<<endl;

        a[i]=-2147483649;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

结束啦~~~