10026. Задача сапожника
Сапожнику необходимо выполнить n работ. Для каждой i - ой работы известно время ее выполнения Ti и штраф Si,
который каждый день должен платить сапожник до тех пор, пока он не отдаст i - ую работу заказчику. Найти
последовательность выполнения работ, при которой сумма штрафа будет
минимальной.
Вход.
Первая строка содержит количество тестов, за которой следует пустая строка.
Первая строка каждого теста содержит число работ n (1 £ n £ 1000).
Следующие n строк содержат
характеристики работ Ti (1
£ Ti £ 1000) и
Si (1 £ Si £ 10000).
Тесты отделяются друг от друга пустой строкой.
Выход. Для каждого теста вывести
порядок работ, при котором сумма штрафа минимальна. При существовании
нескольких оптимальных порядков работ выводить лексикографически наименьший.
Выходные данные последовательных тестов разделять пустой строкой.
Пример входа
1
4
3 4
1 1000
2 2
5 5
Пример выхода
2 1 3 4
РЕШЕНИЕ
жадный алгоритм
Анализ алгоритма
Рассмотрим две работы с
характеристиками T1,
S1 и T2, S2. Если сначала
будет выполняться первая работа, а потом вторая, то сумма штрафа составит
S1 * T1 + S2
* (T1 + T2)
Если за второй будет выполняться
первая работа, то в качестве штрафа следует заплатить
S2 *
T2 + S1 *
(T1 + T2)
Рассмотрим, при каком условии
сумма штрафа при выполнении работ 1, 2 лучше, нежели при выполнении работ в
порядке 2, 1:
S1 * T1 + S2
* (T1 + T2) < S2 *
T2 + S1 *
(T1 + T2)
Раскроем скобки и приведем
подобные:
S2 * T1 < S1 * T2
Или то же самое, что 
.
Пусть теперь имеется n работ. Если существуют i - ая и j - ая работы, для которых Ti
/ Si > Tj / Sj, то поменяв их местами в последовательности выполнения, мы уменьшим общую
сумму штрафа. Таким образом, для минимизации штрафа следует отсортировать
работы по неубыванию отношения времени их выполнения к сумме штрафа.
В случае равенства отношения (Ti
/ Si = Tj
/ Sj), работы следует сортировать по
возрастанию их номеров.
Пример
Отсортируем работы по неубыванию отношения
времени их выполнения к сумме штрафа:
Получим соответственно
оптимальный порядок выполнения работ, указанный в примере.
Реализация алгоритма
Информацию о работах будем
заносить в массив jobs, элементами которого являются
вектора длины 3. После считывания данных jobs[i][0] содержит время выполнения i - ой работы Ti,
jobs[i][1] содержит значение штрафа Si, а jobs[i][2] содержит i.
vector<int> j(3,0);
vector<vector<int> > jobs;
Функция
сортировки. Сравнение 
эквивалентно a[0] * b[1] <
b[0] * a[1]. Если отношения a[0] / b[0] и a[1] / b[1] равны,
то раньше должна следовать работа с меньшим номером. Поэтому в этом случае
следует сравнивать номера работ, которые содержатся в a[2] и b[2].
int lt(vector<int> a, vector<int> b)
{
if (a[0] *
b[1] == b[0] * a[1]) return a[2] < b[2];
return a[0] *
b[1] < b[0] * a[1];
}
Основная
часть программы. Читаем входные данные. Заполняем массив jobs.
scanf("%d",&tests);
while(tests--)
{
scanf("%d",&n);
jobs.clear();
for(i = 1;
i <= n; i++)
{
scanf("%d
%d",&j[0],&j[1]); j[2] = i;
jobs.push_back(j);
}
Сортируем работы согласно функции lt.
sort(jobs.begin(),jobs.end(),lt);
Выводим результат как требуется в условии задачи.
printf("%d",jobs[0][2]);
for(i = 1;
i < n; i++)printf(" %d",jobs[i][2]);
printf("\n");
if (tests)
printf("\n");
}