codechef算法：添加分數

Question

我正在解決在codechef上添加分數：http://www.codechef.com/problems/ADDFRAC/ 問題。 如果有人可以幫助我理解問題的算法，這將是很大的幫助。

P.S：我試過這個問題，但是因爲我的算法是O（n^2），所以我得到超出時間限制。 我的代碼：http://www.codechef.com/viewsolution/2278117

Answer 1

你正在做兩個簡單的for循環。

而你應該做的是開始在相反的方式，並保持計算，直到總和大於當前的總和

如果你看到最多的回答可以看出，該指數是取自N-1到1

計算的推移，直到如果條件滿足 - 即是下一個分數除比當前總和

它存儲這在一個單獨的陣列高達（以指示直到此保持最大折射率true）

for(int index=n-1; index>0; index--) { 
int j=index+1; 
while(j<=n) { 
    next_num=numerator[j]; 
    next_den=denominator[j]; 
    if((1.0*numerator[index])/denominator[index] 
     <(1.0*(numerator[index]+next_num)) 
    /(denominator[index]+next_den)) { 
     numerator[index]=numerator[index]+next_num; 
     denominator[index]=denominator[index]+next_den; 
     j=upto[j]+1; 
//printf("%d/%d ", numerator[index], denominator[index]); 
} else { 
    upto[index]=j-1; 
    break; 
    } 
} 
if(j>n) { 
    upto[index]=n; 
} 
}