配列要素は 1 回の移動で k 位置に移動しますか?

n 個の要素を含む配列があるとします。1 から n までの順序がスクランブルされます。別の整数 K を与えます。 N人がバドミントンをするために並んでいます。最初の 2 人のプレーヤーがボールに行き、その後、負けたプレーヤーがラインの最後に行きます。勝者は次に並んでいる人と対戦します。誰かが K 回連続で勝つまでプレイを続けます。そのプレイヤーが勝者となります。

キューが [2, 1, 3, 4, 5] で K = 2 の場合、出力は 5 になります。ここで説明を見てください:

(2, 1) が一致し、2 が勝利したため、キューに 1 が追加され、キューは [3, 4, 5, 1] (2, 3) になります。一致、3 勝したためキューに 2 が追加され、キューは [4, 5, 1, 2] (3, 4) 一致、4 勝したためキューに 3 が追加され、キューは [5] になります、1、2、3] (4、5) 一致、5 勝なので 4 がキューに追加され、キューは [1、2、3、4] (5、1) 一致、5 勝なので 3 になります。がキューに追加され、キューは [2, 3, 4, 1]

#(2, 1) と一致し、2 が勝利したため、キューに 1 が追加され、キューは [3, 4, 5 , 1]

(2, 3) が一致し、3 が勝利したため、キューに 2 が追加され、キューは [4, 5, 1, 2]

になります。 (3, 4 ) 一致、4 勝なので 3 がキューに追加され、キューは [5, 1, 2, 3]

(4, 5) 一致、5 勝なので 4 になります。がキューに追加されると、キューは [1, 2, 3, 4]

(5, 1) と一致し、5 が勝ちとなるため、キューに 3 が追加され、キューは [2, 3] になります。 , 4, 1 ]

5 が 2 連勝したため、出力は 5 になります。

アルゴリズム

winner(arr, n, k)

Begin
   if k >= n-1, then return n
   best_player := 0
   win_count := 0
   for each element e in arr, do
      if e > best_player, then
         best_player := e
         if e is 0th element, then
            win_count := 1
         end if
      else
         increase win_count by 1
      end if
      if win_count >= k, then
         return best player
     done
   return best player
End

Example

の中国語翻訳は次のとおりです:

Example

#include <iostream>
using namespace std;
int winner(int arr[], int n, int k) {
   if (k >= n - 1) //if K exceeds the array size, then return n
      return n;
   int best_player = 0, win_count = 0; //initially best player and win count is not set
   for (int i = 0; i < n; i++) { //for each member of the array
      if (arr[i] > best_player) { //when arr[i] is better than the best one, update best
         best_player = arr[i];
         if (i) //if i is not the 0th element, set win_count as 1
         win_count = 1;
      }else //otherwise increase win count
      win_count += 1;
      if (win_count >= k) //if the win count is k or more than k, then we have got result
         return best_player;
   }
   return best_player; //otherwise max element will be winner.
}
main() {
   int arr[] = { 3, 1, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout << winner(arr, n, k);
}

出力

rreeee

以上が配列要素は 1 回の移動で k 位置に移動しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。