信息学奥赛一本通T1235：分治算法 输出前k大的数

【题目描述】给定一个数组，统计前k大的数并且把这k个数从大到小输出。【输入】第一行包含一个整数n，表示数组的大小。n < 100000。第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。第三行包含一个整数k，k < n。【输出】从大到小输出前k大的数，每个数一行。【输入样例】10【输出样例】9【源程序】 

信息学奥赛一本通T1235：输出前k大的数

【题目描述】

给定一个数组，统计前k大的数并且把这k个数从大到小输出。

【输入】

第一行包含一个整数n，表示数组的大小。n < 100000。

第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。

第三行包含一个整数k，k < n。

【输出】

从大到小输出前k大的数，每个数一行。

【输入样例】

10
4 5 6 9 8 7 1 2 3 0
5

【输出样例】

9
8
7
6
5

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#define INF 999999999
#define N 1000001
#define MOD 1000000007
using namespace std;

int a[N];

int cmp(const void *a,const void *b){ 
    return (*(int *)a) - (*(int *)b);
}

void Find(int st,int ed,int k){
    if(st-ed+1==k) 
        return;

    int i=st,j=ed,key=a[st];
    while(i<j){
        while(i<j&&a[j]>=key)
            j--;
        a[i]=a[j];
        while(i<j&&a[i]<=key)
            i++;
        a[j]=a[i];
    }
    a[i]=key;
    if(ed-i+1==k)
        return;
    else if(ed-i+1>k)
        Find(i+1,ed,k);
    else
        Find(st,i-1,k-(ed-i+1));
}
int main(){
    int n,k;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    scanf("%d",&k);
    
    Find(0,n-1,k);

    qsort(a+n-k,k,sizeof(a[0]),cmp);
    for(int i=n-1; i>=n-k; i--)
        printf("%d\n",a[i]);
    return 0;
}

 

信息学奥赛一本通T1235：分治算法 输出前k大的数 归属于 分治算法，更多同类题解源程序见：分治算法 和 输出前k大的数

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！