シングルムーブを使用してkによって移動された配列要素？

---

シャッフルされた順序で1からnまでの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になります。

アルゴリズム

勝者（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

例

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

出力

3