1659 - Sort
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
Output
对每组测试数据按从大到小的顺序输出前m大的数。
Examples
Input
5 2 -207693 190069 13569 -48891 -354975 20 6 -339148 446412 -322565 39597 -139187 108119 159993 218397 201075 174963 -149825 137785 105930 -55557 -363362 268859 -139719 -425420 -269331 -333651
Output
190069 13569 446412 268859 218397 201075 174963 159993
Solution C
#include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<time.h> int num[1000005]; int hash( int x ) { return x+ 500000; } int back( int x ) { return x- 500000; } int main( ) { int N, M, cnt, min, max; while( ~scanf( "%d%d", &N, &M ) ) { cnt= 0; min= 0x7fffffff; max= 0x7fffffff+ 1; memset( num, 0, sizeof( num ) ); while( N-- ) { int c; scanf( "%d", &c ); if( min> hash( c ) ) { min= hash( c ); } if( max< hash( c ) ) { max= hash( c ); } num[ hash( c ) ]= 1; } for( int i= max; i>= min; --i ) { if( num[i] ) { cnt++; printf( "%d", back( i ) ); if( cnt< M ) { printf( " " ); } if( cnt== M ) { break; } } } puts( "" ); } }
Solution C++
#include <iostream> #include <string.h> #include <cstdio> 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; int t=num[i]; num[i]=num[j];num[j]=t; while(i<j&&num[i]<key) ++i; 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(){ 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; }