Матч
346, Быстрый почтальон (FastPostman)
Дивизион 2,
Уровень 3
Почтальон должен разнести письма
по домам, расположенным на одной улице. Адреса представляются собой расстояния
от левого конца улицы до домов. Известно граничное время, в течение которого следует
доставить каждое письмо в каждый дом. Скорость почтальона 1 метр в секунду,
доставка писем производится моментально, как только почтальон поравняется с
домом. Необходимо определить, сможет ли почтальон доставить все письма. В
случае утвердительного ответа следует найти наименьшее время, за которое он
сможет это сделать.
Класс: FastPostman
Метод: int
minTime(vector<int> address, vector<int> maxTime,
int initialPos)
Ограничения:
address и maxTime содержат одинаковое количество элементов, не большее 50, 1 £ address[i], initialPos £ 106, 1 £ maxTime[i] £ 109, 1 £ maxTime[i] £ 109.
Вход. Массив адресов домов address и массив maxTime, содержащий граничное время
разноса соответствующих писем. Переменная initialPos
содержит начальное положение почтальона.
Выход. Наименьшее время, за которое почтальон сможет разнести все
письма по указанным адресам с учетом граничного времени. Если он не сможет это
сделать, то вернуть -1.
Пример входа
|
address |
maxTime |
initialPos |
|
{1,3,5,7} |
{9,2,5,100} |
4 |
|
{1,5} |
{6,2} |
3 |
|
{1000000,1000000,1000000,1000000} |
{563,23452,32426,1} |
1000000 |
|
{1000000} |
{45634} |
876 |
Пример выхода
13
6
0
-1
РЕШЕНИЕ
динамическое
программирование
Если почтальон на своем пути
поравняется с некоторым домом, куда следует доставить письмо, то его следует
отдавать сразу же, при первом же подходе к дому. Если почтальон уже разнес
письма в i - ый и j - ый дома, то он точно уже разнес
письма во все дома, которые находятся между i
- ым и j - ым домом. Таким образом,
множество домов, куда уже разнесена почта, представляет собой отрезок прямой с
точкой initialPos внутри. Следует
также отметить, что направление движения почтальон может менять только в точке
с домом, в который он только что доставил письмо.
Состояние почтальона определим
тройкой чисел:
1. левый конец интервала домов,
куда уже разнесена почта;
2. правый конец интервала домов,
куда уже разнесена почта;
3. текущее положение почтальона;
Вместо самих чисел в состоянии
почтальона лучше хранить их индексы в массиве address. На каждом шаге (i,
j, k) следует определить, куда лучше двигаться почтальону: вправо (i, j
+ 1, j + 1) или влево (i – 1, j, i – 1). Также заметим,
что для каждого состояния (i, j, k)
текущее положение почтальона k равно i или j.
В ячейках sol[i][j][0]
будем хранить наименьшее время, за которое почтальон разнесет все письма в дома
в интервале (i, j), причем находиться будет в точке i (в левом конце интервала). Соответственно в sol[i][j][1]
будет содержаться та же информация, только почтальон будет находиться в правом
конце интервала – в точке j.
Отсортируем адреса домов по
возрастанию их координат. Чтобы при сортировке соответствующим образом
переставлялось и граничное время доставки, создадим вектор пар houses, первый
элемент которого содержит адрес дома, а второй – максимальное время доставки
письма в этот дом. При сортировке вектора пар по возрастанию сортировка
производится по первой компоненте – то есть по расстоянию от левого края улицы.
Инициализация массива sol:
sol[i][i][0] = sol[i][i][1]
= | address[i] – initialPos | = | houses[i].first
– initialPos |
Для доставки письма в
единственный дом, индекс которого равен i,
необходимо затратить время, равное расстоянию от начального положения initialPos до местоположения дома
address[i].
Рассмотрим интервал (i, j).
Почтальон может оказаться в его левом конце двигаясь либо с левого конца
интервала (i + 1, j), либо с правого конца интервала (i + 1, j). В первом случае ему требуется пройти расстояние address[i + 1] – address[i], во втором address[j] –
address[i]. То есть
sol[i][j][0] =
= min(sol[i + 1][j][0] + address[i
+ 1] – address[i], sol[i + 1][j][1] +
address[j] – address[i])
Аналогично почтальон может
оказаться в правом конце итервала (i,
j), если он будет двигаться либо с
левого конца интервала (i, j – 1), либо с правого конца интервала (i, j
– 1). В первом случае ему требуется пройти расстояние address[j] –
address[i], во втором address[j]
– address[j – 1]. Таким образом
sol[i][j][1] =
= min(sol[i][ j – 1][0] + address[j]
– address[i], sol[i][ j – 1][1] + address[j]
– address[j – 1])
Если на каком-нибудь этапе
вычисления значение sol[i][j][0] (или sol[i][j][1]) станет большим
maxTime[i] (или соответственно
maxTime[j]), то установим его равным
плюс бесконечности (значению INF = 2000000000). Последнее означает тот факт,
что добраться до соответствующего дома в отведенное время почтальон не может.
Почтальон доставит все письма,
когда будут пройдены все дома из интервала (0, n – 1), где n –
количество домов. При этом нам не важно, в каком из концов этого интервала закончит
путь почтальон. То есть ответом будет значение
min(sol[0][n – 1 ][0], sol[0][n –
1][1])
Если это значение равно плюс
бесконечности, то разнести письма в срок не удастся и следует вернуть -1 как
требуется в условии задачи.
ПРОГРАММА
#include <cstdio>
#include <vector>
#include <memory>
#include <algorithm>
#define INF 2000000000
using namespace std;
int sol[50][50][2];
class FastPostman
{
public:
int minTime(vector<int>
address, vector<int> maxTime, int initialPos)
{
int res, i, j, n = address.size();
vector<pair<int,int> > houses;
for(i = 0; i < n; i++)
houses.push_back(make_pair(address[i],maxTime[i]));
sort(houses.begin(),houses.end());
memset(sol,0,sizeof(sol));
for(i = 0; i < n; i++)
{
sol[i][i][0] = sol[i][i][1] = abs(houses[i].first - initialPos);
if (sol[i][i][0] > houses[i].second)
sol[i][i][0] = sol[i][i][1] = INF;
}
for(i = n - 1; i >= 0; i--)
{
for(j = i + 1; j < n; j++)
{
sol[i][j][0] = min(sol[i+1][j][0] + houses[i+1].first –
houses[i].first,sol[i+1][j][1] + houses[j].first -
houses[i].first);
if (sol[i][j][0] > houses[i].second)
sol[i][j][0] = INF;
sol[i][j][1] = min(sol[i][j-1][0] + houses[j].first - houses[i].first,
sol[i][j-1][1]
+ houses[j].first - houses[j-1].first);
if (sol[i][j][1] > houses[j].second)
sol[i][j][1] = INF;
}
}
res = min(sol[0][n-1][0],sol[0][n-1][1]);
if (res == INF) return
-1;
return res;
}
};