데이터 구조 실험의 정렬 4: 큰 부자 더 미 를 찾 아 정렬

데이터 구조 실험의 정렬 4: 큰 부자 찾기
Time Limit: 200MS
Memory Limit: 512KB
Problem Description
2015 후 룬 글로벌 자산 순위 조사 에 따 르 면 개인 자산 이 1000 만 명 이상 인 고액 순자 산보 유자 가 200 만 명 에 달 하 는 것 으로 나 타 났 다. N 개인의 개인 자산 가 치 를 제시한다 고 가정 하면 상위 M 위의 큰 부 자 를 빨리 찾 아 보 자.
Input
먼저 두 개의 정수 N (N ≤ 10 ^ 6) 과 M (M ≤ 10) 을 입력 하 십시오. 그 중에서 N 은 총 인원수 이 고 M 은 찾 아야 할 큰 부자 수 입 니 다. 그 다음 에 N 개인의 개인 자산 을 드 리 고 만원 단위 로 개인 자산 숫자 는 정수 이 며 숫자 간 은 빈 칸 으로 구 분 됩 니 다.
Output
한 줄 의 데 이 터 는 내림차 순 으로 자산 이 상위 M 위 에 있 는 큰 부자 의 개인 자산 가 치 를 수출 하고 숫자 간 에 빈 칸 으로 구분 되 며 줄 끝 에 빈 칸 이 있어 서 는 안 된다.
 
Example Input

6 3
12 6 56 23 188 60

Example Output

188 60 56

Hint
더미 로 정렬 하여 완성 하 세 요. 
Author
xam
추천 탐색: 백화 고전 알고리즘 시리즈 의 7 더미 와 더미 정렬 + 아하 알고리즘
blablabla: 시간 을 절약 하 는 데 이런 조작 시리즈 가 있다 니...
큰 부자 의 자산 을 많이 보유 하고 있 기 때문에, 몇 개 만 더 저축 하면 된다.저장 하고 정렬 해.
최대 더 미 를 배출 한 후 h [1] 와 h [n] 를 교환 하고 더 미 를 1 로 줄 이 고 h [1] 를 아래로 조정 하여 더 미 를 유지 합 니 다.
마지막 으로 작은 것 부터 큰 것 까지 정렬 하 는 서열 을 얻 었 다.(같은 이치 로 최소 더 미 를 배출 한 후에 큰 것 에서 작은 것 으로 교환 할 수 있다)
1. 정렬 쌓 기 (Aha Algorithms 에서)

#include 
using namespace std;
int h[1011200];
void swap(int x, int y)//  
{
    int t;
    t = h[x];
    h[x] = h[y];
    h[y] = t;
    return ;
}
void siftdown(int i, int n)//    
{
    int t, flag = 0;
    while(i*2 <= n && flag == 0)//         ，        。
    {
        if(h[i] < h[i*2])//        ，          。

        {
            t = i*2;
        }

else t= i; if(i*2+1 <= n && h[t] < h[i*2+1]) { t = i*2+1; } if(t != i) { swap(t, i); i = t; } else flag = 1;//그렇지 않 으 면 현재 아버지 결점 이 두 아들 보다 크다 는 것 을 설명 합 니 다.} return;}void creat (int n) {int i; for (i = n / 2; i > = 1; i - 1; i - - - -) / / / 잎 노드 를 조정 할 필요 가 없 기 때문에 마지막 비 잎 노드 (번호 n / 2) 부터 루트 노드 까지 조정 을 시작 합 니 다. {siftdown (i, n);} return;} void heapsort (int n) / / 쌓 정렬 {whi(n > 1) {swa(1, n); n - -; siftdown (1, n);} ret;} int main () {int main (int m), int i, j, int n, int n; int k = 1 k = 1, int k = 1, k = 1, n, n, n, n, n, n, n, n, n - - - - - - - - -, siftdown; while (cin > > n > > m)/ / 데 이 터 량 을 줄 이기 위해 서 는 앞의 m 개의 큰 부가 가치 만 남 겨 두 고 있 습 니 다. {for (i = 1; i < = n; i + +) {int t; scanf ("% d", & t); if (k < m + 1) h [k + + + +] = t; else {int l = 1; for (j = 2; j h [j]] l] l = j = j;} if (h [l] < t) h [l] h [l] h [l] = t;} int num = n; creat (m); heapsort (m); i = m; i > 1; i - - - - - -) {printf [printf] h [l] h [l] h [l] h [l] h [l] h [l] h [("% d", h [i]);} printf ("% d", h [i]);} return 0;}
2. 빨리 줄 을 서 라
sort 해결...