Giả sử chúng ta có một mảng có n phần tử từ 1 đến n theo thứ tự xáo trộn. Một số nguyên K khác đã cho. Có N dân tộc họ đang xếp hàng để chơi cầu lông. Hai người chơi đầu tiên sẽ chơi, sau đó người thua cuộc sẽ đến và xếp ở cuối hàng đợi. Người chiến thắng sẽ chơi với người tiếp theo từ hàng đợi, v.v. Họ sẽ chơi cho đến khi ai đó thắng K lần liên tiếp. Sau đó, người chơi đó trở thành người chiến thắng.
Nếu hàng đợi giống như [2, 1, 3, 4, 5] và K =2, thì đầu ra sẽ là 5. Bây giờ hãy xem giải thích -
(2, 1) lượt chơi, 2 lượt chơi thắng, do đó 1 lượt sẽ được thêm vào hàng đợi, Hàng đợi giống như [3, 4, 5, 1] (2, 3) lượt chơi, 3 lượt thắng, do đó 2 lượt sẽ được thêm vào hàng đợi, Hàng đợi giống như [4, 5, 1, 2] (3, 4) lượt chơi, 4 chiến thắng, vì vậy 3 lượt sẽ được thêm vào hàng đợi, Hàng đợi giống như [5, 1, 2, 3] (4, 5) lượt chơi, 5 chiến thắng, vì vậy 4 sẽ được thêm vào hàng đợi, Hàng đợi giống như [1, 2, 3, 4] (5, 1) lượt chơi, 5 chiến thắng, vì vậy 3 sẽ được thêm vào hàng đợi, Hàng đợi giống như [2, 3 , 4, 1]
(2, 1) lượt chơi, 2 lượt thắng, vì vậy 1 lượt sẽ được thêm vào hàng đợi, Hàng đợi giống như [3, 4, 5, 1]
(2, 3) lượt chơi, 3 lượt thắng, vì vậy 2 lượt sẽ được thêm vào hàng đợi, Hàng đợi giống như [4, 5, 1, 2]
(3, 4) lượt chơi, 4 chiến thắng, vì vậy 3 sẽ được thêm vào hàng đợi, Hàng đợi giống như [5, 1, 2, 3]
(4, 5) lượt chơi, 5 lượt thắng, do đó 4 lượt sẽ được thêm vào hàng đợi, Hàng đợi giống như [1, 2, 3, 4]
(5, 1) lượt chơi, 5 chiến thắng, vì vậy 3 sẽ được thêm vào hàng đợi, Hàng đợi giống như [2, 3, 4, 1]
như 5 thắng hai trận liên tiếp, thì đầu ra là 5.
Thuật toán
người chiến thắng (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
Ví dụ
#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);
} Đầu ra
3