HDU1425 <sort 快排>

给你n个整数，请按从大到小的顺序输出其中前m大的数。

每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。<快排>

//sort也可以过//936Ms

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=1000005;

int ans[maxn];

bool cmp(int a,int b)

{

    return a>b;

}

int main ()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=0;i<n;i++)

            scanf("%d",&ans[i]);

        sort(ans, ans+n, cmp);

        for(int i=0;i<m-1;i++)

            printf("%d ",ans[i]);

        printf("%d\n",ans[m-1]);

    }

    return 0;

}

//快排1//873Ms

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=1000005;

int ans[maxn];

void quickSort(int l,int r)

{

    if(l>=r)

        return ;

    int i,j;

    for(j=i=l+1;i<=r;i++)

        if(ans[i]>ans[l])

            swap(ans[i],ans[j++]);

    swap(ans[l],ans[--j]);

    quickSort(l, j-1);

    quickSort(j+1, r);

}

/*bool cmp(int a,int b)

{

    return a>b;

}*/

int main ()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=0;i<n;i++)

            scanf("%d",&ans[i]);

        //sort(ans, ans+n, cmp);

        quickSort(0, n-1);

        for(int i=0;i<m-1;i++)

            printf("%d ",ans[i]);

        printf("%d\n",ans[m-1]);

    }

    return 0;

}

//快排2//982ms

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=1000005;

int ans[maxn];

void quickSort(int l,int r)

{

    if(l>=r)

        return ;

    int left=l,right=r,temp=ans[left];

    while(left<right)

    {

        while(left<right&&ans[right]<=temp)

            right--;

        ans[left]=ans[right];

        while(left<right&&ans[left]>=temp)

            left++;

        ans[right]=ans[left];

    }

    ans[left]=temp;

    quickSort(l,left-1);

    quickSort(left+1, r);

}

/*bool cmp(int a,int b)

{

    return a>b;

}*/

int main ()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=0;i<n;i++)

            scanf("%d",&ans[i]);

        //sort(ans, ans+n, cmp);

        quickSort(0, n-1);

        for(int i=0;i<m-1;i++)

            printf("%d ",ans[i]);

        printf("%d\n",ans[m-1]);

    }

    return 0;

}

//快排3//624Ms

#include <iostream>

#include <string.h>

#include <cstdio>

#include<algorithm>

using namespace std;

const int N=1000005;

int num[N];

int partition(int low,int high){

    int i=low,j=high,key=num[low];

    while(i<j){

        while(i<j&&num[j]>key)

            --j;

        swap(num[i],num[j]);

        //int t=num[i]; num[i]=num[j];num[j]=t;

        while(i<j&&num[i]<key)

            ++i;

        swap(num[i],num[j]);

        //t=num[i]; num[i]=num[j];num[j]=t;

        }

    return i;

}

void quick_sort(int low,int high){

    if(low<high){

        int x=partition(low,high);

        quick_sort(low,x-1);

        quick_sort(x+1,high);

    }

}

int main(){

    //freopen("11.txt","r",stdin);

    int n,m;

    while(~scanf("%d%d",&n,&m)){

        for(int i=0;i<n;++i)

            scanf("%d",&num[i]);

        quick_sort(0,n-1);

        for(int i=n-1;i>n-m;--i)

            printf("%d ",num[i]);

        printf("%d",num[n-m]);

        printf("\n");

    }

    return 0;

}

巴特西

HDU1425 <sort 快排>

最新文章

热门文章