На этом шаге рассмотрим применение алгоритма бинарного поиска при решении конкретных задач.
Рассмотрим применение алгоритма бинарного поиска при решении следующей задачи (Региональный этап Всероссийской олимпиалы школьников по информатике 2018г., первый тур).
Задача 1. Улучшение успеваемости
Ограничение по времени: 1 секунда
Ограничение по памяти: 512 мегабайт
В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх. Примеры округления оценок приведены в таблице.
Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок. Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.
Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.
Решение:
Пусть ученик получит x оценок в 5 баллов. Тогда общее число оценок будет равно (a + b + c + x), а средняя оценка будет равна (2a + 3b + 4c + 5x) / (a + b + c + x). По условию задачи должно выполняться условие (2a + 3b + 4c + 5x) / (a + b + c + x) ≥ 3.5.
Каждая дополнительная оценка в 5 баллов увеличивает среднюю оценку, следовательно для поиска минимального значения x, при котором среднее значение не меньше 3.5 можно применить двоичный поиск.
Рассмотрим реализацию задачи средствами языка C++ в среде Qt Creator.
#include <QCoreApplication> #include <bits/stdc++.h> #include <iostream> #include <stdio.h> using namespace std; int main(int argc, char *argv[]) { QCoreApplication ap(argc, argv); FILE *fp, *fout; long long a, b, c, m; fp = fopen ("0","r+"); fscanf (fp, "%lld\n%lld\n%lld", &a, &b, &c); fclose(fp); long long sum = 2 * a + 3 * b + 4 * c; long long cnt = a + b + c; long long l = 0, r = cnt + 1; // Алгоритм бинарного поиска while (l < r) { m = (l + r) / 2; if ((sum + 5.0 * m) / (cnt + m) < 3.5) l = m + 1; else r = m; } fout = fopen ("0.a","w+"); fprintf (fout,"%lld",l); fclose(fout); return ap.exec(); }
Архив с примером на языке С++ можно взять здесь.
Архив с примером на языке Pascal можно взять здесь.
На следующем шаге обсудим время выполнения алгоритма бинарного поиска.
