| Тип задач и общая идея решения | Задачи с разбором | Другие примеры |
|---|---|---|
|
Cканлайн Есть какие-то отрезки. Каждый отрезок открывается в какой-то мемент и закрывается, а что происходит в середине, нам не важно. Тогда давайте сохраним в массиве начало и конец отрезка с указанием типа точки. Затем отсортируем все точки по координате и найдем то, что нужно. |
11484 9847 4336 |
10726 10107 9756 7276 4938 3088 2650 2580 2480 416 7756 9711 9554 9171 9077 8616 8569 |
|
Жадные алгоритмы Идея очень проста. Давайте жадно набирать ответ. Подробнее смотрите примеры |
8961 788 2616 |
8581 6277 9793 5890 5383 5141 4408 3165 2944 2614 2395 2362 2149 1395 1379 1354 1304 1275 1232 1207 1066 |
|
Неявно представить таблицу, найти ряд с каким-то свойством Вместо того, чтобы хранить полностью всю таблицу, давайте сохраним только те элементы, которые важны. Подробнее смотрите примеры |
1868 4115 7456 |
8663 7274 4688 4687 4686 4553 4481 4369 4308 4205 3902 3745 3665 3664 3586 3377 3230 3023 3022 2717 |
|
Каждый k-й товар в полцены Давайте зафиксируем количество товаров, которое мы возьмем. Пусть это количество будет x. А затем x / k максимальных товаров по цене среди первых x в порядке возрастания цены возьмем в полцены. |
6800 |
6759 4684 4660 4629 589 |
|
Соседние различаются на x Отсортируем все элементы по возрастанию, затем жадно наберем ответ. |
7096 |
6071 6096 6056 6031 5988 5918 5643 5497 5446 5066 4712 4604 |
|
Несколько типов товаров Давайте наберем как-то ответ. А затем прорелаксируем ответ так, чтобы максимизировать количество одного товара. |
6641 |
6641 5679 2255 2254 |
|
Наименьшее не превосходящее Отсортируем элементы и зафиксируем минимум/максимум. |
2617 |
2652 4956 316 681 1079 707 1257 636 507 476 107 954 2612 7045 |
| Задачи на подумать | 1763 68 7014 |
2652 4956 316 681 1079 707 1257 636 507 476 107 954 2612 7045 |