1965. Шеренга

Петя Васечкин перешёл в другую школу. На уроке физкультуры ему понадобилось определить своё место в строю...

Вход. Первая строка содержит количество человек n в классе. Затем задана невозрастающая последовательность из n чисел, описывающая рост каждого человека в строю. Затем задан рост x Пети. Все числа натуральные и не превышают 200.

Выход. Выведите номер, под которым Петя должен стать в строй. Если в строю есть люди с одинаковым ростом, таким же, как у Пети, то Петя должен стать после них.

Пример входа 1	Пример выхода 1
8 165 163 160 160 157 157 155 154 162	3
Пример входа 2	Пример выхода 2
8 165 163 160 160 157 157 155 154 160	5

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Входная последовательность уже отсортирована в невозрастающем порядке. Найдем место Пети при помощи бинарного поиска по верхней границе. Нумерация позиций в строю начинается с 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);

Реализация с собственным бинарным поиском

#include <cstdio>

#include <vector>

using namespace std;

int i, n, x, pos;

vector<int> v;

int main(void)

{

scanf("%d",&n);

v.resize(n+1);

for(i = 1; i <= n; i++)

scanf("%d",&v[i]);

scanf("%d",&x);

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);

return 0;

}