描述
给定n个正整数，输出前m小的。
输入
两个整数n （0 < n <= 1000000）和 m  (0 < m <= 1000)
接下来的n行，每行有一个正整数
输出
只有一行，表示前m小的数，注意行末不要有多余的空格
样例输入
6 3
5
6
4
1
2
3
样例输出
1 2 3




#include<iostream>
using namespace std;
void sort(int a[],int n)
{
    int i,j,max;
    for(i=n-1;i>0;i--)
        for(j=0;j<i;j++)
            if(a[j]>a[j+1])
            {
                a[j] = a[j]^a[j+1];
                a[j+1] = a[j+1]^a[j];
                a[j] = a[j]^a[j+1];
            }   
}
int main()
{
    int i,m,n;
    int *p = new int[n];
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d",&p[i]);
    sort(p,n);
    for(i=0;i<m-1;i++)
        printf("%d ",p[i]);
    printf("%d\n",p[m-1]);
    delete []p;
    return 0;
}

排序改成快排，堆排都可以

改成qsort吗？你试过没？

这个还用试啊。。1000000的数据量(n^2)级排序肯定超时的啊

#include<iostream>
#include<cstdlib>
using namespace std;
int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}
int main()
{
    int i,m,n;
    int *p = new int[n];
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d",&p[i]);
    qsort(p,n,sizeof(p[0]),cmp);
    for(i=0;i<m-1;i++)
        printf("%d ",p[i]);
    printf("%d\n",p[m-1]);
    delete []p;
    return 0;
}

大虾们，弄一个高效的算法吧。。。。。。。。

把OJ的网址发下 我去试试

我在杭电上面找了个和这个类似的题目 直接维护一个最小堆就可以了  不过堆用的是STL里面的
http://acm.hdu. 这是亚洲赛区的网络赛题目

#include <stdio.h>
#include <queue>
using namespace std;
struct Node
{
    int a;
    bool operator<(const Node &node1)const
    {return node1.a<a;}
};

int main()
{
    int n,k;
    Node t;
    char c;
    while(EOF != scanf("%d%d",&n,&k))
    {
        getchar();
        priority_queue<Node> pq;
        while(n--)
        {
            int size = 0;
            scanf("%c",&c);
            getchar();
            if('I' == c)
            {
                scanf("%d",&t.a);
                getchar();
                if(pq.size() < k)
                {
                    pq.push(t);
                }
                else if(t.a>(pq.top()).a)
                {
                    pq.pop();
                    pq.push(t);
                }
            }
            else if('Q' == c)
            {
                printf("%d\n",(pq.top()).a);
            }
        }
    }
    return 0;
}

额额 看不懂。。。我改成qsort排序后通过了。。但是效率好低诶。。。

已经过了  拿杭电的改的 维护一个最大堆  代码在帖子里面

#include <stdio.h>
#include <queue>
using namespace std;
struct Node
{
    int a;
    bool operator<(const Node &node1)const
    {return node1.a>a;}
};
int a[1005];
int main()
{
    int n,k;
    Node t;
    priority_queue<Node> pq;
    while(EOF != scanf("%d%d",&n,&k))
    {
        while(!pq.empty())pq.pop();      
        while(n--)
        {
            scanf("%d",&t.a);
            if(pq.size() < k)
                pq.push(t);
            else if(t.a<(pq.top()).a)
            {
                pq.pop();
                pq.push(t);
            }
        }
        int i = 0,j;
        while(k--)
        {
            a[i++] = pq.top().a;
            pq.pop();
        }
        for(j = i-1;j>0;j--)
            printf("%d ",a[j]);
        printf("%d\n",a[j]);
    }
    return 0;
}