Sıra (Həll təhlili)

Giriş ardıcıllığı artıq azalan sırada çeşidlənmişdir. Petyanın mövqeyini yuxarı sərhəd üzrə ikili axtarışla tapacağıq. Sıralamada mövqelərin nömrələnməsi $1$-dən başlayır.

Alqoritmin implementasiyası

Giriş verilənlərini oxuyuruq. Şagirdlərin boyunu $v$ massivinə toplayırıq.

scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
  scanf("%d",&v[i]);
scanf("%d",&x);

Əgər sırada Petyanın boyuna bərabər boylu şagirdlər varsa, o zaman o, onların arxasında durur. Petyanın mövqeyini tapmaq üçün yuxarı sərhəd üzrə ikili axtarışdan istifadə edirik – bu mümkün, çünki massiv azalan sırada çeşidlənmişdir.

pos = upper_bound(v.begin(),v.end(),x,greater<int>()) - v.begin();

Petyanın mövqeyini çıxarırıq və tapşırıqda şagirdlərin nömrələnməsi birlə başladığına diqqət edirik.

printf("%d\n",pos + 1);

Alqoritmin implementasiyası — öz ikili axtarış

Giriş verilənlərini oxuyuruq. Şagirdlərin boyunu $v$ massivinə toplayırıq.

scanf("%d",&n);
v.resize(n+1);
for(i = 1; i <= n; i++)
  scanf("%d",&v[i]);
scanf("%d",&x);

Petya $1$-dən n + 1-ə qədər istənilən mövqeni tuta bilər. İkili axtarış intervalını başladırıq: [Left; Right] = [1; n + 1].

int Left = 1, Right = n + 1, Middle;

İkili axtarışı başladırıq.

while(Left < Right)
{
  Middle = (Left + Right) / 2;
  if (x <= v[Middle]) Left = Middle + 1; else Right = Middle;
}

Cavabı, yəni Petyanın sıradakı mövqeyini çıxarırıq.

printf("%d\n",Left);