算法codechef：添加分数 [英] Algorithm for codechef :Adding Fraction

问题描述

我的工作问题，增加分数： HTTP：//www.$c$cchef .COM /问题/ ADDFRAC / 在codechef。 如果有人能帮助我理解算法的问题，这将是很大的帮助。

I am working on problem Adding Fraction: http://www.codechef.com/problems/ADDFRAC/ at codechef. If someone can help me in understanding algorithm for problem it would be great help.

PS：我想这个问题，但因为我的算法中是O（n ^ 2）我得到的时间超出限制。 我的code： HTTP：//www.$c$cchef.com/viewsolution/2278117

P.S :I tried this problem but since my algo is O(n^2) i am getting Time Limit Exceeded. My code: http://www.codechef.com/viewsolution/2278117

推荐答案

您正在做两个简单的循环。

You are doing it in two simple for loops.

而你应该做的是开始在相反的方式，并保持计算，直到总和大于当前的总和

Whereas what you should do is start in the reverse fashion and keep computing till the sum is greater then the current sum

如果你看到最多的回答可以看出，该指数是从N-1到1

If you see the top answer you can see that the index is taken from n-1 to 1

该计算的推移，直到如果条件满足 - 即是下一个分数加成大于当前总和

The computing goes on till the if condition is met - that is the next fraction addition is greater than the current sum

这将其存储在一个单独的数组高达（指示最大的索引，直到此成立）

It stores this in a separate array upto (to indicate the maximum index till which this holds 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;
 }
}

这篇关于算法codechef：添加分数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！