我是照解題報告的想法做的,但是我的radix sort好像寫壞了,傳上去只有40(NA),最後兩筆tle,想請問一下要怎麼改
#include <bits/stdc++.h>//c223
typedef long long LL;
using namespace std;
const int maxn = 1000005;
LL arr1[maxn] , arr2[maxn] , rs[10][maxn];
void radixSort(int len , int arrlen) {
LL use = 1;
for(int i=0;i<len;i++ , use*=10) {
int cur[10] = {0};
for(int j=0;j<arrlen;j++) {
int lsd = arr1[j] / use % 10;
rs[lsd][cur[lsd]++] = arr1[j];
}
for(int j=0 , now = 0;j<10;j++) {
for(int k=0;k<cur[j];k++)
arr1[now++] = rs[j][k];
}
}
}
int main() {
int n;
while(scanf("%d",&n) == 1 && n) {
LL sum = 0;
int cur1 = n , cur2 = 0 , i = 0 , j = 0 , len = 0;
for(int i=0;i<n;i++) {
scanf("%lld",&arr1[i]);
int use = log10(arr1[i]) + 1;
len = max(len , use);
}
radixSort(len , n);
for(int k=1;k<n;k++) {
LL a , b;
if(arr1[i] < arr2[j] && i < cur1 || j >= cur2) a = arr1[i++];
else a = arr2[j++];
if(arr1[i] < arr2[j] && i < cur1 || j >= cur2) b = arr1[i++];
else b = arr2[j++];
arr2[cur2++] = a + b;
sum += (a + b);
}
printf("%lld\n",sum);
}
return 0;
}