Задача

Есть $n$ городов, стоящих на прямой с запада на восток. Города пронумерованы от $1$ до $n$, в порядке с запада на восток. Каждая точка на прямой имеет свою одномерную координату, и точка ближе к востоку имеет большую координату. Координата $i$-го города — $x_i$.

Сейчас Вы находитесь в $1$ городе, и хотите посетить все города. У вас есть два способа путешествовать:

Ходить по прямой. При этом ваш уровень усталости будет увеличиваться на $a$ единиц каждый раз, когда Вы будете перемещаться на расстояние $1$, независимо от направления.
Телепортироваться в любую точку, которую хотите. Ваш уровень усталости будет увеличиваться на $b$ единиц, независимо от телепортированного расстояния.

Входные данные

Первая строка содержит три числа $n (2 \leqslant n \leqslant 10^5)$, $a$ и $b (1 \leqslant a, b \leqslant 10^9)$. Следующая строка содержит $n$ целых чисел $x_1, x_2, … , x_n (1 \leqslant x_i \leqslant 10^9)$. Для всех $i (1 \leqslant i \leqslant n-1)$ имеет место неравенство $x_i <x_{i+1}$

Выходные данные

Выведите минимально возможный уровень усталости, при котором вы посетите все города.

Решение

Наименьший уровень усталости набирается при кратчайшем пути через все города — последовательном посещении всех городов по порядку и использовании оптимального способа передвижения. Для выбора способа передвижения мы считаем расстояние между следующим пунктом путешествия и нашим нынешним местоположением — $x_{i+1}-x_i$ ($1 \leqslant i \leqslant n-1$). После этого мы сравниваем прибавку к уровню усталости при переходе между городами — $(x_{i+1}-x_i) · a$ и при телепортации $b$, после чего прибавляем меньшее значение к нынешнему уровню усталости.

Тесты

№	Ввод	Вывод
1	4 2 5 1 2 5 7	11
2	7 1 100 40 43 45 105 108 115 124	84
3	7 1 2 24 35 40 68 72 99 103	12
4	5 6 30 100 104 105 192 201	90

Код

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    long long n, a, b, x, x0, fatique = 0;
    cin >> n >> a >> b;
    cin >> x0; //ввод координат первого города
    n--; //поскольку мы в первом городе, нам остаётся посетить n-1 город
    while (n--) {
        cin >> x;
        fatique += min(a * (x - x0), b); //увеличение усталости на меньшую величину
        x0 = x;
    }
    cout << fatique;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long long n, a, b, x, x0, fatique = 0;

cin >> n >> a >> b;

cin >> x0; //ввод координат первого города

n--; //поскольку мы в первом городе, нам остаётся посетить n-1 город

while (n--) {

cin >> x;

fatique += min(a * (x - x0), b); //увеличение усталости на меньшую величину

x0 = x;

}

cout << fatique;

}

Ссылки

Related Images:

Похожее

3 thoughts on “e-olimp 8596. Путешествие с запада на восток”

Не нужно делать каждый символ математической формулы отдельной формулой latex. Это — $i\ \left(1 \geqslant i \geqslant n — 1\right)$ одна формула, а не четыре формулы с текстом между ними.
Выражение «более оптимальный» математически не корректно. «Оптимальный» в математике синоним экстремума (минимума или максимума). В технике означает «наилучший». В обоих случаях добавление сравнительной или превосходной степени недопустимо.
Умножение в математике не обозначается звездочкой.
При описании алгоритма, Вы вдруг неожиданно говорите о функции вычисления максимума из некоторой библиотеки. Это так существенно? Вроде нет. Лучше не путать алгоритм с реализацией его в программе.
Сосредоточьтесь на описании выбранной стратегии движения и доказательстве (или хоть обосновании) ее оптимальности.

Хорошо, только сделайте знаки нестрогих неравенств правильно — \geqslant \leqslant : $A \geqslant B \leqslant C$

Дмитрий Калинин says: 19/01/2019 at 16:44

Благодарю за замечание, исправил.

Добавить комментарий Отменить ответ

Для отправки комментария вам необходимо авторизоваться.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

e-olimp 8596. Путешествие с запада на восток