배열 요소가 한 번의 이동으로 k 위치를 이동했습니까?

n개의 요소를 포함하는 배열이 있다고 가정하면 1부터 n까지의 순서가 뒤섞여 있습니다. 또 다른 정수 K가 주어졌습니다. 배드민턴을 치기 위해 N명이 줄을 서 있습니다. 처음 두 선수는 공을 향해 가고, 패자는 라인 끝으로 이동합니다. 승자는 다음 줄의 사람과 경기를 하게 됩니다. 누군가 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입니다.

algorithm

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

Output

3

위 내용은 배열 요소가 한 번의 이동으로 k 위치를 이동했습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!