PAT B1045 快速排序

题目如下：

1045 快速排序（25 point(s)）

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？

例如给定 $N = 5$, 排列是1、3、2、4、5。则：

1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
类似原因，4 和 5 都可能是主元。

因此，有 3 个元素可能是主元。

输入格式：

输入在第 1 行中给出一个正整数 N（≤105）；第 2 行是空格分隔的 N 个不同的正整数，每个数不超过 109。

输出格式：

在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

5

1 3 2 4 5

输出样例：

3

1 4 5



思路： 只需要判断当前元素 1.大于左边元素中的最大值 2.小于右边元素的最小值　　就可以输出。
　　　 正序遍历，标记满足条件1的元素；再倒序遍历，存储满足条件2且已经被标记的元素。
　　　 输出满足条件1，2的元素。

疑惑：我觉得满足这两个条件的元素按照输入的先后顺序来说肯定是增序的，所以按照输入的先后输出不行吗？
　　　我下面的代码后面几个测试点始终无法通过，有点不解。
　　　希望有大佬帮忙解惑。谢谢。

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <vector>

using namespace std;

int main()

{

    int n, cnt = 0 ;

    int tempMax = 0,tempMin = 1000000001;

    int numArray[100001] = {0};

    bool masterUnitFlag[100001] = {false};

    scanf("%d", &n);

    //输入数据  同时进行正序判断

    for(int i = 0; i < n; ++ i)

    {

        scanf("%d", &numArray[i]);

        if(numArray[i] > tempMax)

        {

            tempMax = numArray[i];

            ++ cnt;

            masterUnitFlag[i] = true;

        }

        else

        {

            masterUnitFlag[i] = false;

        }

    }

    for(int i = n - 1; i >= 0; -- i)

    {

        //逆序判断

        if(numArray[i] >= tempMin)

        {

            -- cnt;

            masterUnitFlag[i] = false;

        }

        else

        {

            tempMin = numArray[i];

//            if(masterUnitFlag[i])

//                disNum.push_back(tempMin);

        }

    }

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

    bool symbolFlag = false;

    if(cnt > 0)

    {

        for(int i = 0; i < n; ++ i)

        {

            if(masterUnitFlag[i])

            {

                if(symbolFlag)

                    printf(" ");

                printf("%d",numArray[i]);

                symbolFlag = true;

            }

        }

    }

    else

        printf("\n");

//    sort(disNum.begin(), disNum.end());

//    if(cnt > 0)

//    {

//        for(int i = 0; i < cnt; ++ i)

//        {

//            if(symbolFlag)

//                printf(" ");

//            printf("%d",disNum[i]);

//            symbolFlag = true;

//        }

//    }

//    else

//        printf("\n");

    return 0;

}

巴特西

PAT B1045 快速排序

输入格式：

输出格式：

输入样例：

输出样例：

最新文章

热门文章