0

このプログラムの目標は、配列内のすべての数値を同じにすることです。毎回 1 つを除いて、配列内のすべての値をインクリメントする必要があります。次に、プログラムは、すべての数値を同じにするために必要な最小ステップ数を出力します。私はそれをより効率的にしたいだけの実用的なソリューションであると信じています。誰かアイデアはありますか? 次のコードでは、ユーザーは数値の初期値を配列に入力し、必要なステップ数を計算します。

public static void main(String[] args) throws NumberFormatException, IOException 
{
counter=0;
         size=sc.nextInt();
         input= new int[size];
        for(int k=0; k<size; k++)
        {
            input[k]=sc.nextInt();
        }
        while(!isAllEqual(input))
        {
            Arrays.sort(input);
            for(int k=0; k<input.length-1; k++)
            {
                input[k]++;
            }
            counter++;
        }
        pw.println(counter);

public static boolean isAllEqual(int[] a){
    for(int i=1; i<a.length; i++){
        if(a[0] != a[i]){
            return false;
        }
    }
return true;
}
4

2 に答える 2

6

ステップをもっと単純なものに変更すると、頭を包み込むのが簡単になるかもしれません。値の間の等価性 (つまり、絶対値ではなく相対値) についてのみ話している場合、すべての値を一度に増減しても違いはありません。ステップを「1 を除いてすべてインクリメントし、すべての値を 1 ずつ減らす」に変更すると、1 を除くすべての値をインクリメントすることは、1 つの値をデクリメントすることと同じであることがわかります。

ステップが「値を1つ減らす」場合、値を等しくするためのステップ数を把握できますか? 配列を最大で 2 回ループし、並べ替えを行わない必要があります。

于 2013-01-01T22:55:42.820 に答える
3

質問を読み違えたので大幅に編集

リストを一度だけスキャンして、リスト内の最小値と、すべての値を合計した合計を見つけます。

これら 2 つの値を取得したら、必要な増分の数は次のようになります。

[すべての値の合計] - [リスト内のアイテムの数] * [最小値]

コード内:

public static int numberOfSteps(int[] a) {
    if( a.length==0 ) return 0;

    int min= a[0];
    int total = a[0];
    for(int i=1;i<a.length;i++) {
        if( a[i] < min ) min = a[i];
        total += a[i];
    }

    return total - a.length * min;
}

(Matti Virkkunen が指摘したように) 各項目の減少数は(a[i] - min )、リスト全体でsum(a[i]-min)に拡張できるため、これが機能しsum(a[i]-(length*min)ます。

対応するインクリメントは、最大値に等しい右端のアイテムを除くすべてをインクリメントするために、各ステップにあります。例えば：

初期状態 = (0,1,1,1) 1. a[3] 以外のすべてをインクリメント --> (1,2,2,1) 2. a[2] 以外のすべてをインクリメント --> (2,3, 2,2) 3. a[1] 以外のすべてをインクリメント --> (3,3,3,3) : 3 つのステップでの解 = (1+1+1) - (4 * 0)

再び、(1,2,3,3) の初期状態

  1. a[3] 以外のすべてをインクリメント --> (2,3,4,3)
  2. a[2] 以外のすべてをインクリメント --> (3,4,4,4)
  3. a[3] 以外のすべてをインクリメント --> (4,5,5,4)
  4. a[2] 以外のすべてをインクリメント --> (5,6,5,5)
  5. a[1] 以外のすべてをインクリメント --> (6,6,6,6) : 5 つのステップで解決 = (1+2+3+3) - (4 * 1)
于 2013-01-01T22:57:59.520 に答える