algorithm - codechef的算法：添加分数

Question

我正在解决添加分数的问题：http: //www.codechef.com/problems/ADDFRAC/ at codechef。如果有人可以帮助我理解问题的算法，那将是很大的帮助。

PS：我尝试了这个问题，但由于我的算法是 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;
 }
}