Встретил задачку:
Есть N (3 ≤ N ≤ 10000) длин отрезков. Нужно выбрать 3 с них так, что бы полученный треугольник имел наименьшую площадь и вывести ее.
Прошу помочь ибо нету никаких идей.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.12.2024 09:49:51 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Если зафиксировать 2 стороны, то синус угла между ними нужно минимизировать, т.е третью сторону минимизировать или максимизировать. То есть нужно попробовать 2 варианта: минимальная сторона больше b — a и максимальная меньше a+b
спасибо, но даже при лучшем раскладе выходит O(n^2).
Ну да, квадрат и выходит, если делать 2 указателя.
У вас же ограничения под квадрат явно
Там ТЛ 500мс, и сервер слабенький
UPD Прошу прощения,все таки ТЛ 2с
Так что, это решение подходит или можно ещё подумать? Учтите ещё, что можно перебирать только один из двух указанных вариантов. А ещё какие длины сторон-то? Если целые и ≤ k, где k не слишком большое, то можно за O(k + n) найти всевозможные суммы, а потом за O(k + n) же найти для каждой суммы s ближайшую к ней длину отрезка < s.
Длины отрезков до 20000, и заданы нам квадраты длин отрезков
Сначала отсортируем массив по возростанию. Далее перебираем три последовательных числа с помощью for. Если из трех можно составить треугольник выводим эти числа. P.S. Являются ли отрезки треугольником можно проверить с помощью if(a+b>c&&b+c>a&&a+c>b&&abs(a-b)<c&&abs(a-c)<b&&abs(b-c)<a)
Объясните, пожалуйста, почему это будет работать?
Нет я хотел сказать одним for перебираем три последовательных отрезка. вот код.
а на тесте
4
1 2 10 10
работает?
Не будет работать на тесте 1+eps, 2, 4, 5.
Выкинуть нужно 2
Если я правильно понял условие, то вот решение за O(n2).
У нас не больше 2N различных точек — концов отрезков. Построим граф: точки — вершины, а ребра — отрезки. Будем хранить в остортированном виде в какую точку мы можем попасть из текущей.
Переберем отрезок. У нас уже есть 2 точки треугольника, нужно определить третью. Для этого объединим, в какую третью точку мы можем попасть и из первой, и из второй одновременно (слить два отсортированных списка). Получили списочек треугольков, которые мы можем получить исспользуя 2 текущие точки (точки от выбранного отрезка) и еще третью (из слитых списков). Итого O(n2), только не ясно, тут квадрат подойдет или надо быстрее.
UPD: То, что я написал, разве не работает за линию? Ведь количество ребер у нас O(n), тогда в сумме сливание списков будет линейное же?
прошу прощения, я не объяснил, даны не точки,а длины отрезков.Виноват
Ясно, тогда я не в тему написал)
вот та же задача, но уже с ограничением n <= 1e5: http://acmp.ru/index.asp?main=task&id_task=594
у меня зашло решение, которое ищет ответ только среди 150 самых длинных отрезков, но это вроде неправда
там максимальная площадь,а если я не ошибаюсь она максимальна если брать соседние стороны
Извиняюсь, не увидел, что минимальная площадь нужна
Допустим мы отсортируем все длины отрезков. Не будут тогда нужные нам треугольники вида i, j, j + 1, где i < j?
Допустим стороны нашего треугольника имеют индексы i, j, k и i < j < k. Допустим i и k зафиксированны, тогда очевидно, что j должно быть как можно больше (чтобы высота была как можно меньше у треугольника, за основание отрезок k возьмем). Получается, что при заданных i и k и условии i < j < k либо a[i], a[j = k - 1], a[k] треугольник с минимальной площадью при фиксированных i и k (если правило треугольника соблюдается), либо такого нет.
Если так то, можно просто перебирать j, брать две стороны a[j], a[j + 1] и искать такое минимальное i, что a[i] > a[j + 1] - a[j].
Тест: 5 7 9 10
5 7 10 даёт площадь лучше, чем 5 9 10
"очевидно, что j должно быть как можно больше"
Быть может, все-таки "как можно меньше"?
Да, так и есть: как можно меньше и чтобы выполнялось неравенство треугольника. Выше HellKitsune тест, собственно, предоставил, которой показывает, что мое изначальное утверждение не корректно.
https://www.dropbox.com/s/ljywzxkwf11gx75/Sbornik_2010.pdf?dl=0
Надеюсь страница 100 поможет в решении.
Пусть вырожденный треугольник по условию подходит. То есть, если есть такие i, j, k : a[i] + a[j] = a[k], нужно их уметь искать. Это аналог задачи 3-SUM. Задача эта хорошо изучена, быстрее чем за Θ(n2) её решать не умеют.
А лучшее по константе решение за Θ(n2) -- как раз описанный в первом посте метод двух указателей.
Кстати, на современных серваках 109 простых операций заходят за секунду. 108 зайдёт даже за 0.5 даже на очень слабом сервере.
UPD: 3-SUM при ограниченных числах решается через быстрое умножение многочленов. Если числа целые от 1 до C, для решения исходной задачи нам достаточно насчитать для каждой суммы двух сторон a+b, f[a+b] = max(b-a). После этого задача решится за O(C).