Elemen tatasusunan memindahkan k kedudukan dengan satu langkah?

Andaikan kita mempunyai tatasusunan yang mengandungi n elemen, susunan dari 1 hingga n dikacau. Diberi satu lagi integer K. Terdapat N orang beratur untuk bermain badminton. Dua pemain pertama akan pergi ke bola, kemudian yang kalah akan pergi ke hujung garisan. Pemenang akan memainkan orang seterusnya dalam barisan dan seterusnya. Mereka akan terus bermain sehingga seseorang memenangi K kali berturut-turut. Pemain itu kemudian menjadi pemenang.

Jika baris gilir ialah [2, 1, 3, 4, 5] dan K = 2, maka keluarannya ialah 5. Sekarang lihat penjelasan:

(2, 1) perlawanan, 2 kemenangan, jadi 1 akan ditambah pada baris gilir, dan baris gilir menjadi [3, 4, 5, 1] ​​​​(2, 3) perlawanan, 3 menang, jadi 2 akan ditambah pada baris gilir dan baris gilir menjadi [4, 5, 1, 2] (3, 4) padanan, 4 kemenangan, jadi 3 akan ditambah pada baris gilir dan baris gilir menjadi [5, 1, 2, 3] (4, 5) Perlawanan, 5 menang, jadi 4 akan ditambah pada baris gilir, baris gilir menjadi [1, 2, 3, 4] (5, 1) Perlawanan, 5 menang, jadi 3 akan ditambah ke baris gilir, Gilir menjadi [2, 3, 4, 1]

(2, 1) padanan, 2 menang, jadi 1 akan ditambah pada baris gilir, baris gilir menjadi [3, 4, 5, 1]

(2, 3) Perlawanan, 3 kemenangan, jadi 2 akan ditambah pada baris gilir, baris gilir menjadi [4, 5, 1, 2]

(3, 4) Perlawanan, 4 kemenangan, jadi 3 akan ditambah ke baris gilir, baris gilir menjadi [5, 1, 2, 3]

(4, 5) perlumbaan, 5 menang, jadi 4 akan ditambah pada baris gilir, baris gilir menjadi [1, 2, 3, 4]

( 5, 1 ) permainan, 5 kemenangan, jadi 3 akan ditambahkan pada baris gilir, dan baris gilir menjadi [2, 3, 4, 1]

Memandangkan 5 menang dua perlawanan berturut-turut, output ialah 5. Terjemahan bahasa Cina bagi

algoritma

pemenang(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

Contoh

ialah:

Contoh

#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

Atas ialah kandungan terperinci Elemen tatasusunan memindahkan k kedudukan dengan satu langkah?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!