POJ 2388 基数排序

这题可以直接nth_element过去

比如这样子

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

int n,a[100500];

int main(){

    scanf("%d",&n);

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

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

    nth_element(a+1,a+n/2+1,a+1+n);

    printf("%d\n",a[n/2+1]);

}

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define int unsigned int

int a[10000005],b[10000005],sum[65536],too[65536],n;

signed main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%u",&a[i]);

    for(int i=1;i<=n;i++)sum[(a[i]<<16)>>16]++;

    for(int i=1;i<65536;i++)too[i]=too[i-1]+sum[i-1];

    for(int i=1;i<=n;i++){

        int x=(a[i]<<16)>>16;

        too[x]++,b[too[x]]=a[i];

    }

    memset(sum,0,sizeof(sum));

    for(int i=1;i<=n;i++)sum[b[i]>>16]++;

    too[0]=0;

    for(int i=1;i<65536;i++)too[i]=too[i-1]+sum[i-1];

    for(int i=1;i<=n;i++){

        int x=b[i]>>16;

        too[x]++,a[too[x]]=b[i];

    }

    printf("%u\n",a[n/2+1]);

}