配列が非減少になるように配列を変更するには、以下の解決策で何が問題になっていますか？

Question

私が期待しているのは、正確な答えではなく、私が解決策を改善する方法です。 現在のところ、テストケースが1つでもなくても間違っています。 1つのケースでは間違った答えを出し、他のものはタイムアウトを示します。 [ - 1 I] < A [i]はiが[2、N]に属する場合、そのようなサイズの配列A N.そのアレイに変換することを考える

通報

。この配列の任意の要素に任意の回数Xを追加できます。私たちの仕事は、A [i-1] < A [i]条件を満たすためにXの追加の最小数が必要であることを伝えることです。

入力

入力の最初の行は、Tを含有するであろう（いいえ。テストケースの）。 すべてのテストケースについて、最初の行には、NとXを示す2つのスペースで区切られた整数が含まれます。次の行にはA [i]を表すN個のスペースで区切られた整数が含まれます。すべてのテストケースについては

出力

、新しい行に必要な答えを印刷します。

サンプル入力

2 // Total Number of Test Cases 
2 1 // First value is N and second is X 
1 1 // Elements of the first Array 
3 1 // First value is N and second is X for the second array 
1 1 2 // Elements of the second array 

サンプル出力

1 
2 

私の解決策： - 上記のコードが生成された答えは上記のサンプル入力の場合

import java.io.BufferedReader; 
import java.io.InputStreamReader; 
import java.util.Arrays; 


class TestClass { 
    public static void main(String args[]) throws Exception { 

     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     String line = br.readLine(); 
     int T = Integer.parseInt(line);// Total number of Test Cases 
     int N = 0;// Number of elements in the Array 
     int X = 0;// The number which can be added to the elements of the array 
     int[] arr; 
     int count;// Final count value which needs to be shown 
     while(T-->0) { 
      String[] str = br.readLine().trim().split("\\s+"); 
      N= Integer.parseInt(str[0]); 
      X = Integer.parseInt(str[1]); 
      arr = new int[N]; 
      str = br.readLine().trim().split("\\s+"); 
      count = 0; 
      for(int i = 0; i < N; i++){ 
       arr[i] = Integer.parseInt(str[i]); 
      } 

      for(int i = 1; i < N ; i++){ 
       while(arr[i - 1] >= arr[i]){ 
        arr[i] += X; 
        count++; 
       } 
      } 
      System.out.println(count); 
     } 


    } 
} 

対応ctを使用しますが、オンラインジャッジによって隠されてタイムアウトになる他のケースでは失敗します。 これを修正するには？

Answer 1

2つの潜在的な問題：

まず、forループ内にwhileループがあります。ループの代わりにdivisonを使って直接反復回数を計算できるはずです。これはタイムアウトを避けるべきです。

kを使用してwhileループの反復回数を表します。 我々は

A[i]+k*x > A[i-1]. 

したがって、我々はループの周りの反復回数がとして計算することができる整数演算を使用して

k > (A[i-1]-A[i])/x 

を推定できることを知っている：整数に注意して、第二に

k = (A[i-1]-A[i]+x)/x if A[i] <= A[i-1], or 0 otherwise 

オーバーフロー。 XとNの大きさはどれくらいかは不明ですが、最大値がintデータ型をオーバーフローしないことを確認してください。