假设我们有一个数组,其中包含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连续赢得两场比赛,所以输出是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
的中文翻译为:示例
'#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