Новогодние и рождественские праздники прошли, поэтому давайте разберём задачу про мытьё посуды с сайта acmp.ru.
Переходя от легенды задачи на язык математики, нам надо найти такой x, чтобы функция суммарного расстояния до заданных точек на плоскости была минимальна, то есть
Аналитически это решать не очень просто, потому что надо найти производную, приравнять её к нулю и решить сложное уравнение. Поэтому давайте решать численно. Для поиска минимума функции можно применить тернарный поиск: разбиваем отрезок, на котором ищем ответ, двумя точками на три части, вычисляем значение функции в этих точках и отбрасываем один из кусков в зависимости от значений функции.
В зависимости от способа выбора точек, которыми бьётся отрезок, можно получить тернарный поиск (отрезок разбивается на три одинаковые части), Фибоначчиев поиск (отрезок разбивается на части, пропорциональные числам Фибоначчи) и метод золотого сечения (отрезок разбивается на части, пропорциональные золотому сечению). Первый из них самый простой в реализации, второй гарантирует лучшую точность при заданном количестве итераций, а третий позволяет переиспользовать вычисленные значения функции на следующих итерациях (это бывает полезно, если вычисление функции очень долгое).
В нашем случае достаточно будет самого простого, поэтому давайте приступать к решению.
Определим и подключим библиотеки, которые нам понадобятся. А также заведём две подстановки, чтобы можно было использовать pair, но не терять в читаемости кода.
После этого можно считать данные:
Несмотря на то, что входные данные являются целыми числами, я завёл вектор для вещественных чисел по двум причинам:
- нам надо будет передавать их в функцию sqrt для вычисления квадратного корня, для этого потребуется явное привидение типов,
- для вычисления расстояния надо будет возводить в квадрат, а входные значения до миллиона, поэтому они не поместятся в тип int.
Использование сразу типа double, решает обе проблемы. Но будьте с этим аккуратны, я ни раз говорил, что использование вещественных чисел чревато накоплением погрешности. В нашем решении вычисление функции будет происходить каждый раз заново, да и ответ можно выводить с точностью до единиц, что позволяет нам такую роскошь.
Основное решение задачи состоит из тернарного поиска, в котором всё стандартно. Вложенным циклом вычисляем значение функции в точках a и b. Цикл прерывается, когда отрезок становится не больше 0.1, это то значение, которое задаёт точность, с которой ищется ответ. По условию задачи можно было выбрать число и по-больше, что уменьшило бы число итераций цикла и ускорило работу программы, но решение на C++ и так укладывается с двукратным запасом.
Выводим ответ с шестью знаками после запятой на всякий случай, чтобы какое-нибудь округление до целого не сломало наше решение.
Заметим, что выводить можно любое из чисел l и r (и любое число между ними), потому что они отличаются от правильного ответа не более чем на 0.1, а по условию задачи этого более чем достаточно.
Предыдущий выпуск: Задача 20. Пилообразная последовательность
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.