直接做洛谷上面的快拍模板。。用了个log的小优化，时间瞬间优化三分之一。。
1 #include <cstdio> 2 using namespace std; 3 //#define debug 4 5 #ifdef debug 6 const int maxn=20; 7 #else 8 const int maxn=1e5+5; 9 #endif 10 11 double log210; 12 int n, maxlen; 13 int a[maxn]; 14 int bucket[10][maxn]; 15 16 double log2(float x){ 17 return ((((unsigned int&)x>>23)&255)-127); 18 } 19 20 int len(int x){ 21 return log2(x)/log210+1; 22 } 23 24 int main(){ 25 log210=log2(10); 26 scanf("%d", &n); 27 int l; 28 for (int i=0; i<n; ++i) { 29 scanf("%d", &a[i]); 30 l=len(a[i]); 31 if (l>maxlen) maxlen=l; 32 } 33 int num, len, alen=0; 34 for (int i=0, m=1; i<maxlen; ++i, m*=10){ 35 for (int j=0; j<10; ++j) bucket[j][0]=0; 36 for (int j=0; j<n; ++j){ 37 num=a[j]/m%10; 38 len=++bucket[num][0]; 39 bucket[num][len]=a[j]; 40 } 41 alen=0; 42 for (int j=0; j<10; ++j) 43 for (int k=1; k<=bucket[j][0]; ++k) 44 a[alen++]=bucket[j][k]; 45 } 46 for (int i=0; i<n; ++i) 47 printf("%d ", a[i]); 48 return 0; 49 }