Шеренга (Розбір)

Вхідна послідовність вже відсортована в невозростаючому порядку. Знайдемо позицію Петі за допомогою бінарного пошуку по верхній межі. Нумерація позицій у строю починається з $1$.

Реалізація алгоритму

Читаємо вхідні дані. Заносимо зріст школярів в масив $v$.

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

Якщо в строю є школярі зі зростом, рівним зросту Петі, він стає після них. Для пошуку позиції Петі використовуємо бінарний пошук по верхній межі – це можливо, оскільки масив відсортований в невозростаючому порядку.

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

Виводимо позицію Петі, враховуючи, що в задачі нумерація школярів починається з одиниці.

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

Реалізація алгоритму — власний бінарний пошук

Читаємо вхідні дані. Заносимо зріст школярів в масив $v$.

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

Петя може зайняти будь-яку позицію від $1$ до n + 1. Ініціалізуємо інтервал бінарного пошуку: [Left; Right] = [1; n + 1].

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

Запускаємо бінарний пошук.

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

Виводимо відповідь — позицію Петі в строю.

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