PAT (Advanced Level) Practice 1101 Quick Sort (25 分) 凌宸1642

2023-11-08 16:32:04

PAT (Advanced Level) Practice 1101 Quick Sort (25 分) 凌宸1642

题目描述：

There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?

For example, given N=5 and the numbers 1, 3, 2, 4, and 5. We have:

1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;
3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;
2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;
and for the similar reason, 4 and 5 could also be the pivot.

Hence in total there are 3 pivot candidates.

译：著名的快速排序算法中有一个名为partition的经典过程。在这个过程中，我们通常选择一个元素作为枢轴。然后将小于枢轴的元素移到其左侧，将大于枢轴的元素移到其右侧。在分区运行后给定 N 个不同的正整数，您能说出有多少元素可以作为该分区的选定主元吗？

例如，给定 N = 5 ，并且给定序列 1 , 3 , 2 , 4 , 5 ，有：

1 可能是枢轴，因为它的左边没有元素，并且右边的所有元素都比它大。
3 一定不是枢轴，虽然在它左边的数字都比它小，但是其右边的 2 也比它小；
2 一定不是枢轴，虽然在它右边的数字都比它大，但是其左边的 3 也比它大；
同理，4 和 5 都可能是枢轴。

因此，总共有三个枢轴候选者。

Input Specification (输入说明):

Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 10⁵). Then the next line contains N distinct positive integers no larger than (≤ 10⁹). The numbers in a line are separated by spaces.

译：每个输入文件包含一个测试用例。对于每种情况，第一行给出一个正整数 N (≤ 10⁵)。然后在下一行给出 N 个不大于 10⁹ 的正整数，并用空格分隔。

output Specification (输出说明):

For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

译：对于每种情况，在第一行打印枢轴候选者的数量。然后在第二行，按升序输出所有枢轴候选者。两个数字之间必须正好有一个空格分隔，并且行尾不能有多余的空格。

Sample Input (样例输入):

5
1 3 2 4 5

Sample Output (样例输出):

3
1 4 5

The Idea：

思路，根据题意，能作为枢轴的数字，其左边的数字都比它小，右边的数字都比它大，所以将所有数字按照升序排序后，可以作为枢轴的数字，其在数组中的位置不会变。
- 仅仅是位置不变是不够的，因为可以出现这种情况，在数字序列 1 5 2 4 3中，排序之后的序列为1 2 3 4 5 ，其中数字 1 和4的位置都没有发生变化，但是能够满足题题目意思的枢轴的候选者只有1。这也就产生了作为枢轴候选者的第二个条件：枢轴候选者左边的最大值比枢轴小 (因为题目中说明了 N 个不同的数字)
记录所有满足上述条件的数字，并按题目要求输出即可。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 100010 ;
int a[maxn] , b[maxn];
vector<int> res ;
int n , t , ans , preMax ; 
int main(){
	scanf("%d" , &n) ;
	for(int i = 0 ; i < n ; i ++){
		scanf("%d" , &t) ;
		b[i] = a[i] = t ;
	}
	sort(b , b + n) ;
	if(a[0] == b[0]) {
		ans ++ ;
		res.push_back(b[0]) ;
		preMax = a[0] ;
	} 
	for(int i = 1 ; i < n ; i ++){
		if(a[i] > preMax) preMax = a[i] ; // 记录区间 [0 , i] 之间数组的最大值
		if(b[i] == a[i]){ // 位置未发生变化， 且为 [0 , i]内最大值，则为枢轴候选者
			if(b[i] == preMax) { 
				preMax = b[i] ;
				ans ++ ;
				res.push_back(b[i]) ;
			}
		}
	}
	printf("%d\n" , ans) ;
	for(int i = 0 ; i < ans ; i ++)
		printf("%d%c" , res[i] , ((i == ans -1)?'\n':' ')) ;
	if(ans == 0) printf("\n") ; // 有一个测试点为没有枢轴候选者的情况
	return 0 ;
}

码农公寓