Les éléments du tableau ont été déplacés de k positions d'un seul mouvement ?

Supposons que nous ayons un tableau contenant n éléments, l'ordre de 1 à n est brouillé. Étant donné un autre entier K. Il y a N personnes qui font la queue pour jouer au badminton. Les deux premiers joueurs iront au ballon, puis le perdant ira au bout de la ligne. Le gagnant jouera contre la personne suivante en ligne et ainsi de suite. Ils continueront à jouer jusqu'à ce que quelqu'un gagne K fois de suite. Ce joueur devient alors le gagnant.

Si la file d'attente est [2, 1, 3, 4, 5] et K = 2, alors la sortie sera 5. Regardez maintenant l'explication :

(2, 1) matchs, 2 victoires, donc 1 sera ajouté à la file d'attente, et la file d'attente devient [3, 4, 5, 1] ​​​​(2, 3) matchs, 3 gagne, donc 2 seront ajoutés à la file d'attente et la file d'attente devient [4, 5, 1, 2] (3, 4) matchs, 4 victoires, donc 3 seront ajoutés à la file d'attente et la file d'attente devient [5, 1, 2, 3] (4, 5) match, 5 victoires, donc 4 seront ajoutés à la file d'attente, la file d'attente devient [1, 2, 3, 4] (5, 1) match, 5 victoires, donc 3 seront ajoutés à la file d'attente, La file d'attente devient [2, 3, 4, 1]

(2, 1) matchs, 2 victoires, donc 1 sera ajouté à la file d'attente, la file d'attente devient [3, 4, 5, 1]

(2, 3) Match, 3 victoires, donc 2 seront ajoutés à la file d'attente, la file d'attente devient [4, 5, 1, 2]

(3, 4) Match, 4 victoires, donc 3 seront ajoutés à la file d'attente, la file d'attente devient [5, 1, 2, 3]

(4, 5) course, 5 victoires, donc 4 seront ajoutées à la file d'attente, la file d'attente devient [1, 2, 3, 4]

( 5, 1) jeu, 5 victoires, donc 3 seront ajoutés à la file d'attente, et la file d'attente devient [2, 3, 4, 1]

Puisque 5 gagne deux jeux d'affilée, le résultat est 5. La traduction chinoise de

algorithme

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

est :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!