趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 amoshuangyc 於 2014-8-30 15:07 編輯
這題的一般作法是請參考這。補充一點,在求中位數時,可以不用 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 |