sdnuoj 1060 找第K大数

发布时间：2020-12-14 04:10:01 所属栏目：大数据来源：网络整理

导读：1060.找第K大数 Time Limit: 1000 MS????Memory Limit: 32768 KB Total Submission(s): 109????Accepted Submission(s): 22 Description 给定 n(1 = n = 10000000) 个正整数(= 2147483647)，找出其中的第K(1 = K = 10)大数。 Input 第一行，两个整数n,K，第

1060.找第K大数

Time Limit: 1000 MS????Memory Limit: 32768 KB
Total Submission(s): 109????Accepted Submission(s): 22

Description

给定 n(1 <= n <= 10000000) 个正整数(<= 2147483647)，找出其中的第K(1 <= K <= 10)大数。

Input

第一行，两个整数n,K，第二行n个整数

Output

第K大数

Sample Input

5 3
10 15 6 8 3

Sample Output

TOP K算法 堆排序
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
int n,k;
int dui[101];
void duipai(int i){
    int t1=2*i;
    int t2=t1+1;
    int pos,temp;
    if(t1>k) return;
    else{
        if(t2>k)
            pos=t2;
        else
            pos=dui[t1]>dui[t2]?t2:t1;
        if(dui[i]>dui[pos]){
            temp=dui[i];
            dui[i]=dui[pos];
            dui[pos]=temp;
            duipai(pos);
        }
    }
}
void create(){
    int pos=k/2;
    int i;
    for(i=pos;i>=1;i--)
        duipai(i);
}
int main(){
    int i,tmp;
    scanf("%d%d",&n,&k);
    for(i=1;i<=k;i++)
        scanf("%d",&dui[i]);
    create();
    for(i=k+1;i<=n;i++){
        scanf("%d",&tmp);
        if(tmp>dui[1]){
            dui[1]=tmp;
            duipai(1);
        }
    }
    printf("%dn",dui[1]);
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!