Lutece Problem 528-输出前m大的数

题目

原题地址
利用快排的思想，首先将前m的数移至数组右边，然后用内置sort函数对这m个数排序，最后输出即可。
为什么不能直接全局sort，然后输出m个数呢？因为这样的题目数组特别大，复杂度特别高。这里我们运用快排的思想找到前m大的数只花费了的时间，另外排序花了，总复杂度为，比小很多。

#include <iostream>
#include <algorithm>

using namespace std;
#define maxn 1000100
int A[maxn];
int n,m;

//将数组l到r位置前k大的数移到l到r位置的右边
void move_right(int *A, int l, int r, int k){
    if(l>r) return;
    int i=l,j=r;
    int key=A[l];
    while(i!=j){
        if(i<j&&A[j]>=key) --j;
        swap(A[i],A[j]);
        if(i<j&&A[i]<=key) ++i;
        swap(A[i],A[j]);
    }
    int len = r-i+1;
    if(len==k) return;
    else if(len>k) move_right(A, i+1, r, k);
    else move_right(A,l,i-1,k-len);
}

int main()
{
    while(cin>>n>>m){
        for(int i=0; i<n;i++) cin >> A[i];
        //memset(A, 0, sizeof(A));
        move_right(A,0,n-1,m);
        sort(A+n-m,A+n); //将右边的m个数升序排序
        for(int i=n-1;i>=n-m;i--) cout << A[i] << " ";
    }
    return 0;
}