PAT~乙级~1045 快速排序 ~C++

淩亂°似流年 2021-11-29 15:56 212阅读 0赞

题目描述：

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 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

\----------------------------------------------------------答题区----------------------------------------------------------

题目中有个比较关键的字眼，就是这N个数字是不同的。可以使用两个数组把数存储起来，对其中的一个进行排序，然后在循环中对这两个数组进行比较，因为每个数都不相同，所以比他大的数的个数和比他小的数的个数是确定的，要想满足主元要求，那在未排序的数组中和已排序的数组中的位置序号应是一样的。

其次还要比较一下，这个数前面是否有比他大的数，如果有，则他的后面也必然有比他小的数，这就不满足主元要求了。

测试点2是主元个数为0的情况，因为题目要求输出两行，故要另输出一行，只不过输出的内容为空。

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int main()
    {
        int num,num1,left_max=0;
        vector <int> vi;
        scanf("%d",&num);
        int a[num],b[num];
        int i=0,flag_num=0;
        num1 = num;
        while(num1--)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
            ++i;
        }
        sort(a,a+num);
        for(int i=0;i<num;i++)
        {
            if(a[i]==b[i] && left_max<b[i])
            {
                vi.push_back(b[i]);
                flag_num++;
            }
            if(b[i] > left_max)
            {
                left_max = b[i];
            }
        }
        if(flag_num!=0)
        {
            printf("%d\n",flag_num);
            sort(vi.begin(),vi.end());
            for(vector<int>::iterator it = vi.begin();it!=vi.end();it++)
            {
                if(it==vi.begin())
                {
                    printf("%d",*it);
                }
                else
                {
                    printf(" %d",*it);
                }
            }
        }
        else
        {
            printf("0\n");
            printf("\n");
        }
        return 0;
    }

维护了一个PAT测试点问题的共享文档，欢迎大家把遇到的问题写在上面。

一起写文档：[https://yiqixie.com/d/home/fcACe6xZ2aroPxFQrQZ05Cw32][https_yiqixie.com_d_home_fcACe6xZ2aroPxFQrQZ05Cw32]  
github链接：[https://github.com/Makerdd/PAT-yiji][https_github.com_Makerdd_PAT-yiji]

[https_yiqixie.com_d_home_fcACe6xZ2aroPxFQrQZ05Cw32]: https://yiqixie.com/d/home/fcACe6xZ2aroPxFQrQZ05Cw32
[https_github.com_Makerdd_PAT-yiji]: https://github.com/Makerdd/PAT-yiji