algorithm - codechef のアルゴリズム : 分数の追加

Question

問題の追加分数に取り組んでいます: http://www.codechef.com/problems/ADDFRAC/ codechef で。誰かが問題のアルゴリズムを理解するのを手伝ってくれるなら、それは大きな助けになるでしょう.

PS : この問題を試してみましたが、アルゴが O(n^2) であるため、時間制限を超えています。私のコード: http://www.codechef.com/viewsolution/2278117

Answer 1

2 つの単純な for ループで実行しています。

あなたがすべきことは、逆の方法で開始し、合計が現在の合計よりも大きくなるまで計算を続けることです

一番上の回答を見ると、インデックスが n-1 から 1 になっていることがわかります

計算は if 条件が満たされるまで続きます。つまり、次の分数の加算が現在の合計よりも大きい場合です。

これを別の配列 upto に格納します (これが成り立つ最大インデックスを示すため)。

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