1에서 n까지 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입니다.
알고리즘
승자(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