#14969: 求救~~


i610494 (wago)

學校 : 國立嘉義高級中學
編號 : 68247
來源 : [114.136.228.105]
最後登入時間 :
2021-11-13 12:57:44
c223. Add All(變異版) -- UVA | From: [220.143.105.90] | 發表日期 : 2018-08-24 11:36

我是照解題報告的想法做的,但是我的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;
}

 
ZeroJudge Forum