코덱에 대한 알고리즘 : 분수 추가

Question

문제를 더하고 분수를 추가 : http://www.codechef.com/problems/ADDFRAC/ codechef에서 일하고 있습니다. 누군가가 문제 알고리즘을 이해하는데 도움이된다면 도움이 될 것입니다.

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; 
} 
}