1101.Quick Sort

题目分析

Input：
第一行：一个正整数N（N<=100000）
第二行：N个互不相同的正整数，用空格分隔
Output：
第一行：符合条件的数的个数
第二行：按照升序输出

求解思路

• int类型的数组arr[N]：存放了原始数据
• maxBefore：当前左侧最大值（初始化为-1）
• minBehind：当前右侧最小值（初始化为1000000005）
• int类型的数组res[N]：存放结果
• bool类型的数组flag[N]：flag[i]指示arr[i]是否为我们要找的元素，若是，flag[i]=true；否则flag[i]=false。

1. 在输入的时候，假设当前输入为arr[i]，判断arr[i]是否大于maxBefore，同时更新maxBefore和flag[i]的值。
2. 逆序遍历数组，判断arr[i]是否小于minBehind，若不是，将flag[i]的值更新为false。若此时flag[i]为true，则arr[i]为我们要找的元素，存入res数组中。
3. 输出时，若sum为0，则输出空的一行（必须输出空的一行，否则有的样例不能通过）；若sum不为0，调用sort()函数，将res数组升序排列后输出。

C++源码

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int N;
    int sum = 0;
    cin>>N;
    bool *flag = new bool[N];
    int *arr = new int[N];
    int *res = new int[N];
    int maxBefore = -1;
    int minBehind = 1000000005;

    for(int i = 0; i < N; i++)
    {
        flag[i] = true;
    }

    for(int i = 0; i < N; i++)
    {
        cin>>arr[i];
        if(arr[i] > maxBefore)
        {
            maxBefore = arr[i];
        }
        else
        {
            flag[i] = false;
        }
    }
    for(int i = N - 1; i >= 0; i--)
    {
        if(arr[i] < minBehind)
        {
            minBehind = arr[i];
        }
        else
        {
            flag[i] = false;
        }
        if(flag[i])
        {
            sum = sum + 1;
            res[sum - 1] = arr[i];
        }
    }
    cout<<sum<<endl;
    if(sum == 0)
    {
        cout<<endl;
    }
    else
    {
        //res[0..sum-1]
        sort(res, res + sum);
        for(int i = 0; i < sum; i++)
        {
            cout<<res[i];
            if(i != sum - 1)
            {
                cout<<" ";
            }
        }
    }
    return 0;
}