PAT(Basic Level) Practise(중국어) 1045.빠른 정렬(25)C 언어
시간 제한
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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
PAT A 1049. Counting Ones (30)제목 The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal fo...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.