codechef :Adding Fraction 的算法

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

计算一直持续到满足 if 条件 - 即下一个分数加法大于当前总和

它将它存储在一个单独的数组中直到(以指示它成立的最大索引)

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