TOJ 1 The Repeater

amoshuangyc

這題的一般作法是請參考這。補充一點，在求中位數時，可以不用 sort，直接使用 algorithm 中 nth_element，期望時間複雜度是 O(n)。


但根據某 toj 管理員，有人（吳宗達，toj 1 Rank #1）給出了更快的解法，就我們的解讀，發現他使用了 counting sort ，並只求一次中位數，一個很神奇的做法…
可是我們無法理解為什麼這樣的解法可以 AC。

以下附上該程式碼。
對於吳宗達，很抱歉未經授權就直接貼上，如果你希望我們撤下，我們會立即刪除這篇文章。
但我們希望你可以來詳細解說這個做法，如果可以，我們甚至希望你在解題分享的版塊中發表該解法（這樣你才會獲得應有的論壇積分）。
當然，如果有其它人參悟了其中的奧妙，也歡迎為我們解答！

[C++] 純文本查看 復制代碼

 #include<stdio.h>
#include<string.h>
  
int A[2000][5000] ;
int count[5030] ;
int main(){
    //freopen("test.txt","r",stdin) ;
    int T ,N ;
    scanf("%d",&T ) ;
    char in[5030] ,first[5030];
    for (int t=1 ;t<=T && printf("Case #%d: ",t);t++ ){
        scanf("%d",&N ) ;
        //set_first ---------
        int L=0 ;
        gets(in);gets(in) ;
        first[L]=in[0];A[0][0]=1 ;
        for (int i=1 ,l=strlen(in);i<l;i++ ){
            if (in[i]==in[i-1])A[0][L]++ ;
            else {
                L++ ;
                first[L]=in[i] ;
                A[0][L]=1 ;
            }
        }
        //set_else ----------
        int i=1 ,ok=1 ;
        for (i ;i< N && ok ;i++){
            A[i][0]=1 ;
            int r=0 ;
            gets(in) ;
            //
            if (in[0]!=first[0]){
                i++ ;
                ok=0 ;
                break ;
            }
            //
            for (int j=1 ,l=strlen(in);j<l;j++ ){
                if (in[j]==in[j-1]){
                    A[i][r]++ ;
                    continue ;
                }
                r++ ;
                if (in[j]!=first[r]){
                    ok=0 ;
                    break ;
                }
                else A[i][r]=1 ;
            }
            if (r!=L)ok=0 ;
        }
        //sort --------------
        if (ok==0){
            for (;i<N;i++)gets(in) ;
            puts("Fegla Won") ;
        }
        else {
            int Ans=0 ;
            for (int i=0 ;i<=L ;i++ ){
            //find Me ---
                memset(count,0,sizeof(count)) ;
                for (int j=0 ;j<N ;j++ ){
                    count[ A[j][i] ]++ ;
                }
                int mid=(N+1)/2 ,Me ;
                for (int j=1 ;j<=5000; j++ ){
                    mid-=count[j] ;
                    if (mid<=0){
                    Me=j ;
                    break ;
                    }
                }
                for (int j=1 ;j<Me;j++ )Ans+=count[j]*(Me-j) ;
                for (int j=Me ;j<=5000;j++ )Ans+=count[j]*(j-Me) ;
            }
            printf("%d\n",Ans) ;
        }
    }
}

協助排版
By Sylveon

吳宗達@FB

被周找來 第一次用竹園
只是單純用count把各個出現的次數桶排序（2000log 2000>5000)STL O(n)的話覺得是係數太大了
可以教我code怎麼配色嗎

amoshuangyc

大致理解了，之前誤以為你的程式只求一次中位數= =。
這是個很好的想法，謝謝你的解釋！

要貼程式碼可參考這裡。