Задача
Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть [latex]N[/latex] прямых отрезков.
Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.
Задание
Напишите программу, которая по информации об отрезках найдет наименьшую стоимость трех отрезков, из которых мальчик может сложить треугольник, либо определит, что это сделать невозможно.
Входные данные:
В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].
Выходные данные:
Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 4 1 1 2 2 3 3 4 4 |
9 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <algorithm> #include <vector> #include <climits> using namespace std; //Структура для представления одного отрезка struct Line { int price; int length; }; //Функция сортировщик по цене в порядке возрастания bool comparator_price (Line i, Line j) { return i.price < j.price; } int main() { int n, price, length, cheapest = INT_MAX; cin >> n; Line lines_by_price[n]; for (int i = 0; i < n; i++) { Line l; cin >> length >> price; l.price = price; l.length = length; lines_by_price[i] = l; } //Сортируем все отрезки по цене, чтобы была возможность "отсечь" //слишком дорогие отрезки, когда цена одного(или двух) будет //больше текущей минимальной sort(&lines_by_price[0], &lines_by_price[n], comparator_price); for (int i = 0; i < n; i++) { Line first_side = lines_by_price[i]; if (first_side.price > cheapest) break; vector<Line> sides = {}; //Перебираем все возможные тройки отрезков, отсекая //слишком дорогие, основываясь на сортировке по цене //и текущей минимальной цене for (int j = 0; j < n; j++) { if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) { sides.push_back(lines_by_price[j]); Line second_side = lines_by_price[j]; if (first_side.price + second_side.price > cheapest) break; for (auto third_side: sides) { if ((third_side.length != second_side.length && third_side.price != second_side.price) && first_side.length < second_side.length + third_side.length && second_side.length < first_side.length + third_side.length && third_side.length < second_side.length + first_side.length) { if (first_side.price + second_side.price + third_side.price < cheapest) { cheapest = first_side.price + second_side.price + third_side.price; } break; } } } } } //Если ни одна тройка отрезков не подошла, значит составить //треугольник невозможно - выводим "-1" if (cheapest == INT_MAX) cheapest = -1; cout << cheapest; return 0; } |
Решение
Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.
— Лучше писать не $Li$, а $L_i$. А то можно перепутать с китайской фамилией 🙂
— Что-то $10^9$ у вас не получилось записать.
— Не забывайте ставить пробелы между словами. Перед открывающей скобкой тоже.
— Если я правильно понял, вычислительная сложность у вас $O(n^3)$. А быстрее никак?
— Ошибки по оформлению исправил
— В наихудшем случае, то есть если единственным возможным вариантом треугольника будут самые дорогие отрезки, сложность будет [latex]O(n^3)[/latex], но во всех остальных случаях значительная часть отрезков просто не будет перебираться из-за того, что цены отсортированы по возрастанию составляют подстановку. Таким образом, количество переборов уменьшается в несколько десятков раз. Варианта быстрее придумать не смог, хотя и этот работает в два раза быстрее лимита по времени.
А с номером задачи вы не ошиблись?
Исправил, видимо остался с прошлой задачи. Также по поводу вычислительной сложности из предыдущего комментария: данная структура не является матроидом, насколько я понял, поэтому жадные алгоритмы тут применить бы и не получилось.
Код на ideone.com по ссылке в конце статьи не совпадает с кодом, приведенным в тексте статьи (количество строк разное)
Поправил