重複の可能性:
バブル ソートでのスワップの数
問題を以下に簡単に説明します。N 個
の整数の配列 A が与えられた場合、配列の各要素は、ある確率p [ i ]、0 <= i < nで固定数bだけ増やすことができます。バブルソートを使用して配列をソートするために行われるスワップの予想数を見つける必要があります。
私は次のことを試しました：
1) i < jの要素 A[ i ] > A[ j ] の確率は、与えられた確率から簡単に計算できます。2) 上記を使用して、予想されるスワップ数を次のように計算しました。
double ans = 0.0;
for ( int i = 0; i < N-1; i++ ){
for ( int j = i+1; j < N; j++ ) {
ans += get_prob(A[i], A[j]); // Computes the probability of A[i]>A[j] for i < j.
基本的に、スワップの予想数は配列の反転数によって計算できるため、このアイデアに行き着きました。したがって、与えられた確率を利用して、数値 A[ i ] が数値 A[ j ]と交換されるかどうかを計算しています。
以前に同様の質問を投稿しましたが、すべての制約がありませんでした。
私が正しい軌道に乗っているかどうかにかかわらず、良いヒントが得られなかったので、ここにすべての制約をリストしました。問題を間違った方法で考えている場合は、ヒントを教えてください。