PAT(Basic Level) Practise(중국어) 1045.빠른 정렬(25)C 언어

1045. 빠른 정렬(25)
시간 제한
200 ms
메모리 제한
65536 kB
코드 길이 제한
8000 B
판정 절차
Standard
작자
CAO, Peng
유명한 빠른 정렬 알고리즘에는 고전적인 구분 과정이 있다. 우리는 보통 어떤 방법으로 원소를 주원으로 하고 교환을 통해 주원보다 작은 원소를 왼쪽에 놓고 주원보다 큰 원소를 오른쪽에 놓는다.구분된 N개의 서로 다른 정수의 배열을 정합니다. 몇 개의 원소가 구분하기 전에 선택한 주원일 수 있습니까?
예를 들어 주어진 N = 5의 배열은 1, 3, 2, 4, 5이다.다음을 수행합니다.
1의 왼쪽에는 원소가 없고 오른쪽의 원소는 모두 그것보다 크기 때문에 주원일 수 있다.
비록 3의 왼쪽 원소는 모두 그것보다 작지만, 오른쪽의 2는 작기 때문에 주원이 될 수 없다.
비록 2의 오른쪽 원소는 모두 그것보다 크지만, 왼쪽의 3은 그것보다 크기 때문에 그것은 주원이 될 수 없다.
유사한 원인으로 4와 5가 주원일 수도 있다.
따라서 세 개의 원소가 주원일 수 있다.
입력 형식:
1행에 양의 정수 N을 입력합니다(<=105).두 번째 줄은 공백으로 구분된 N개의 서로 다른 정수로 각각 109를 넘지 않는다.
출력 형식:
첫 번째 줄에서 출력은 주원의 원소 개수일 수 있다.두 번째 줄에서 이 요소들을 점차적으로 출력합니다. 그 사이는 한 개의 빈칸으로 구분되며, 줄 끝에 여분의 빈칸이 있어서는 안 됩니다.
샘플 입력:
5
1 3 2 4 5

출력 예제:
3
1 4 5

코드 커밋
#include
#include
typedef struct node
{
	int date;
	int flag;
}aNode;
int cmp(const void *a,const void *b);
int main()
{
	int N,i,n=0;
	int max,min;
	scanf("%d",&N);
	aNode *A=malloc(N*sizeof(aNode));
	int *B=malloc(N*sizeof(int));
	for(i=0;i=max)
		{
			max=A[i].date;
		}else
		{
			A[i].flag=0;
		}
	}
	for(i=N-1;i>=0;i--)
	{
		if(A[i].date<=min)
		{
			min=A[i].date;
		}else
		{
			A[i].flag=0;
		}
	}
	for(i=0;i

좋은 웹페이지 즐겨찾기