Формальное условие:
Нам дано N <= 10^6 отрезков(полуинтервалов) нужно найти:
1)Максимальное количество отрезков, которые мы можем выбрать так, что никакие 2 не будут пересечаться.
2)Среди всех подходящих множеств отрезков найти такое, что у самого левого отрезка в множестве правая
граница минимальна, и вывести эту правую границу.
Решение:
Для того, чтобы найти максимальное количество попарно неперсекающихся отрезков воспользуемся следующим
жадным олгаритмом:
1)Отсортируем все данные отрезки по неубыванию правой границы
2)Будем идти по отсортированному массиву и брать отрезок только в том случае, если он не пересекается с
предыдущим взятым.
Кроме того заметим, что мы автоматически нашли такое множество, в котором наименьшая правая граница
минимальна,
так как первый отрезок в сортировке всегда попадает в разбиение, а у него самая маленькая правая граница из
имеющихся отрезков.
Доказательство корректности:
Пускай мы изначально взяли какое-то множество отрезков и первый отрезок в этом множестве не с минимальной
правой границей.
Тогда мы можем вместо первого отрезка из множества взять отрезок с минимальной правой границей и ответ не
ухудшится.
Зачем мы убираем из рассмотрения все отрезки, которые пересекаются с первым и повторяем рассуждение.
Получается при нашем алгоритме мы получшим ответ не хуже выбранного множества.
Формальное условие:
Нам дано N <= 10^5 отрезков(полуинтервалов) нужно найти:
1)Максимальное количество отрезков, которые покрывают какую-то точку.
2)Найти количество отрезков, состоящих из точек, которые покрываются максимальным количеством отрезков.
Решение:
Для решение этой задачи мы могли выспользоваться таким же алгоритмом, что и в прошлых задачах:
отсортировать отрезки или точки открытия/закрытия отрезков и поддерживать количество открытых отрезков.
Но в данной задаче маленькое ограничение на границы отрезков (<=1440).
Это дает нам возможность решать задачу за линейное время относительно суммы длинн отрезков, а именно:
1)Для всех x из отрезка [start end) мы прибавляем в массиве countOfVisitors к элементу x единицу
2)Проходимся по этому массиву и находим максимум, затем находим количество отрезков, на которых достигается
максимум.
Формальное условие:
Нам дано N <= 10^6 отрезков(полуинтервалов) нужно найти:
1)Количество таких отрезков из точек, которые не покрывает ни один из данных отрезков
2)Суммарную длинну таких отрезков
Решение:
Универсальное решение задач такого типа - это сканлайн.
Суть сканлайна в том, что у нас есть набор некоторых событий, мы их сортируем по времени, а затем проходимся
по ним в этом порядке и поддерживаем некоторые величины.
В данной задаче у нас 2 типа событий: открытие отрезка и закрытие отрезка.
Добавим их в событий events
events.push_back(make_pair(visitors[i].first, -1));
events.push_back(make_pair(visitors[i].second, 1));
добавляем пары вида
{x, -1} для открывающихся отрезков или {x, 1} для закрывающихся
открывающимся соответсвует число -1, потому что при сортировке при равных координатах открытие отрезка
должно идти раньше закрытия.
После сортировки идем по событиям и поддерживаем open - количество открытых отрезков last - последняя
закрытая граница
И насчитываем нужные нам величины
Формальное условие:
Нам дано N <= 2000 заявок из x зрителей, которые нужно посадить подряд на одном ряду.
Нам нужно для каждой заявки выбрать минимальный ряд, на который мы можем посадить каждую следующую заявку.
Садим заявки по неубыванию количесва людей в заявке.
Нужно найти:
1)Сколько заявок сможем усадить
2)Количество оставшихся мест после того, как всех усадили
Решение:
Просто сделаем, что написано в условии:
1)отсортируем данный массив в порядке неубывания.
2)заведем другой массив (q), где q[i] - это количество свободных мест в каждом ряду, изначально заполним его
m.
3)будем идти по массиву заявок и для каджой заявки за O(k) находить первоую позицию j, для которой q[j] >=
a[i].
4)когда нашли вычитаем из количество оставшихся мест a[i] и прибавляем к количеству посаженых заявок 1.
Условие:
Файлы меньше чем 500Мб помещаем на диск E, остальные на диск D.
Найти:
1)Сколько суммарно можно поместить файлов на диски
2)Сумма двух максимальных по размеру файлов на дисках
Решение:
Будем жадно брать самый минимальный файл в каждую из групп.
Очевидно, это не хуже чем брать какие-то большие файлы.
Для этого:
1)Отсортируем, данный в условии массив.
2)с помощью встроенного бинпоиска(lower_bound) находим такой индекс, который соответствует минимальноу
эелеиенту >= 500
3)За линейное время найдем нужный перфикс эелементов
4)Чтобы найти максимальный последний элемент, проходим по всем эелементам < 500 (для диска Е) и пытаемся его
заменить на первый(минимальный) взятый эелемент и проверяем возможно ли это сделать
Условие:
Дано n видов товаров, для каждого вида товаров требуется взять максимальное количество единиц этого товара
так, чтобы суммарный вес не превышал s
Посчитать:
1)Количество невзятых единиц товваров
2)Тип товара, которого при заданых условиях мы можем взять меньше всего.
Решение:
Для каждого типа товара сохраним в map'e вектор всех весов товаров этого типа.
Сортируем вектора для каждого типа.
Удаляем элементы из вектора из конца и считаем их сумму пока сумма не превысит s.
Cчитаем нужные величины.
Условие:
Даны занятые в зале места в виде пары (ряд; место).
Нужно найти максимальный ряд и минимальное место в этом ряду, для которого выполняется, что это место
свободно, рядом с ним есть свободное место, слево и справа от этих двух свободных мест есть 2 занятых
мета.
Решение:
Фактически нам нужно найти в каком-то ряду два занятых места на расстоянии ровно 3.
Для каждого ряда сохраняем в массиве занятые на этом ряду места.
Проходимся по рядам по возрастанию номера ряда.
Сортируем места в каждом ряду.
Проходимся по местам по убыванию номера места.
Если встречаем такое занятое место, что ровно через 2 клетки от него есть занятое, то обновляем ответ.
Такой порядок обхода мест дает нам макимальный ряд и минимальное место с выполнеными условиями.
Формальное условие:
Даны отмеченые клетки матрицы
Нужно найти максимальное количество подряд идущих отмеченых клеток в одном ряду и минимальный номер ряда, в котором это количетсво достигается.
Решение:
Для каждого ряда сохраняем в вектор отмеченые в этом ряду клетки
Проходимся по рядав в порядке возрастания рядов
Сортируем все отмеченые клетки в ряду
Проходимя и насчитываем максимальную длину ряда и подряд идущих клеток(подробности в коде)
Условие:
Даны занятые места на стадионе в виде пары (ряд; место)
Найти:
1)Количество хороших мест
2)Ряд с самым большим номером, на котором есть хотя бы одно хорошее место
Место называется хорошим, если РОВНО через 5 мест справа и слева от него есть занятое место, а все места на меньшем расстоянии свободны.
Решение:
Сначала заведем вектор, где для каждого ряда будем хранить вектор, занятых в нем мест
Потом будем проходиться по рядам по возрастанию номера, сортировать номера мест на ряду и проверять ряд на наличие хороших мест
Условие:
Даны балансы счетов N <= 10000 клиентов
Нужно разделить клиентов на премиум сегмент и обычных сегмент так, чтобы
1)Клиентов премиум сегметов было хотя бы 20 процентов
2)Разница между максимальным балансом клиента обычного сегмента и минимальным балансом клиента в премиум сегмента была максимальна.
3)Клиентов премиум сегмента как можно меньше.
Решение:
1)Сортируем балансы клиентов
2)Идем по возрасанию балансов
3)Предполагаем, что iй клиент имеет максимальный баланс в обычнойм сегменте, а (i + 1) - минимальный в премиум сегменте
В таком случае количество людей в премиум сегменте cntPremium = n - i + 1
Проверяем, что cntPremium / n >= 0.2
*Чтобы не использовать вещественные числа, производим сравнение cntPremium * 10 >= 2 * n
4)Во время процесса максимизируем пару (разница между Min_Prem - Max_Reg, Индекс минимального индекса премиум клиента)
5)с помощью второго элемента пары мы можем получить оба ответа(как, смотрите в коде)
Условие:
Дано N <= 10000 квадратных коробок, для каждой известен ее размер.
Одну коробку можно поместить в другую, если их размеры различаются хотя бы на K = 11
Найти:
1)Максимальное количество коробок, которые можно сложить друг друга в виде матрешки.
2)Максимальный размер минимальной коробки при максимальном количестве коробок.
Решение:
1)Отсортируем коробки по возрастанию размера.
2)Будем идти по убыванию размеров и жадно брать первую коробку для которой выполняется a[i] <= last - K, где last - размер последней коробки.
Жадность работает так как если мы будем брать не первую попавшуюся коробку, мы не увеличим ответ. К тому же при таком решении мы автоматичеcки найдем максимальный размер минимальной коробки.
Условие:
Дано N <= 10^4 товаров, для каждого известа его цена, четное число
Найти
1)максимальное количесво товаров, которые мы можем купить если мы можем потратить не более S = 100000 рублей, а также при условии,
что каждый K-й (K = 6) товар нам достается вполцены. При этом порядок товаров мы можем выбрать сами.
2)Максимальное количество денег, которое у нас при этом останется.
Решение:
1)Зафиксируем ответ. То есть максимальное количество товаров, которое мы возьмем(пусть x).
2)Хотим понять, каких x товаров нам нужно взять, а из этих x, какие взять по цене в 2 раза меньше.
3)Очевидно выгодно взять x самых дешевых товаров. Для этого сортируем массив цен.
4)Теперь осталось выяснить какие из этих товаров брать по цене в 2 раза меньше, очевидно это x / K (челочисленое деление) самых дорогих товаров из этих x.
5)Теперь проходимася по первым x - x / K элементам и суммируем их, а потом по элементам c x - x / K + 1 по x и берем их сумму, деленую на 2.
6)Поймем, что если мы нашли такой максимальный x, то мы автоматически нашли ответ и на воторой вопрос, как как всегда брали наименьшую из возможных сумм.
Мы получили решение за O(n^2)
Можно его оптимизировать до O(nlogn), если фиксировать x с помощью бинарного поиска. Мы можем это сделать, так как функция затрат является монотонно возрастающей. (Вы можете видеть здесь обе версии решения)
Условие:
Дано n кусков оптоволокна. Нужно их соединить в куски длиной x. Если длина при соединении получилась больше x, то лишнее обрезается и обрезок возращается к остальным кускам.
Рабочий действует так:
Он берет сначала самые большие куски, а последний кусок выбирает так, чтобы минимизировать то, сколько он обрежет. Сколько будет всего сварок и сколько придется суммарно отрезать?
Решение:
Нам по сути ничего не нужно минимизировать/максимизировать. Просто реализуем, что написано в условии.
1)Будем пытаться собрать навый кусок длины x, если суммарная оставшаяся длина кусков хотя бы x.
2)Далее приваривем к имеющимся у нас уже кускам новый если длина < x.
3)Сначала пытаемся найти кусок x - we_have.
4)Если такого нет, то просто берем самый большой.
Подробней смотри в коде
Формальное словие:
Дано n чисел.
Нужно вывести максимальное количество пар, которые в сумме дают ровно 100.
Решение:
1)Считаем количество каждого числа x в данном массиве.
2)Если мы зафиксируем минимальное из двух чисел, которых должно давать сумму, то у нас 2 варианта.
3)Если число < 50, то пар с таким минимальным числом будет ровно min(cnt[x], cnt[100 - x])
4)Если число =50, то таких пар cnt[50] / 2 с округлением вниз
5)Если число > 0, то мы учли все такие пары при рассмотрении первого случая.
Условие:
Есть n дней, для каждого известна цена бабочки в этот день
Каждый день у нас появляется новая бабочка
Мы можем продать бабочку начиная с того дня, когда она у нас появилась.
Сколько максимум мы можем заработать? Какой максимальный зароботок при этом мог быть за один день.
Решение:
Поймем, что если бабочка появилась в день i, то нам выгоднее всего продать ее в день, когда достигается максимум на соответствующем суффиксе массива дней.
Мы всегда можем продать в этот день, поэтому все что нам нужно для получения первого ответа это посчитать сумму элементов массива суффиксных максимумов.
Теперь ответ на второй вопрос задачи.
Для того чтобы максимизировать количество заработка в какой-то день(тк цена бабочки не может быть отрицательной), нам нужно максимизировать количество бабочек, проданный в этот день. Для этого будем считать, что если мы продали бабочку по цене x, то мы продели ее в самый последний день, в который она продавалась по этой цене. Понятно, что мы всегда можем это сделать так как если мы не можем выбрать самый правый с ценой x для этой бабочки, то мы не можем выбрать никакой с такой ценой (x либо не является суффиксным максимумом, либо он левее дня, когда появилась бабочка)
Для реализации решения
1) посчитаем суфф. максимумы в массиве цен
2) пройдемся по нему и для каждого x сохраним в map , сколько раз x являлся суффиксным максимумом.
Условие:
Есть товары двух типов и сумма денег, которая у нас есть.
Нужно набрать как можно больше единиц товара.
При одинаковом значении единиц, нужно максимизировать количество товара типа S. При этом нужно потратить как можно меньше денег.
Решение:
Понятно, что чтобы максимизировать количество товаров, в каждый момент выгоднее брать самый дешевый товар.
Возьмем некоторое количество самых дешевых товаров.
Потом нам нужно максимизировать кол-во товаров типа S.
Для того чтобы мы могли сделать как можно больше замен, будем брать самый дешевый доступный товар типа S и будем менять его на самый дорогой из доступных товаров типа W.
Будем делать так до тех пор, пока у нас не кончаться деньги.
Для реализации этого решения поступим так:
Будем хранить отдельно 2 вектора: с ценами товаров типа S и W.
Отсортируем оба вектора.
Будем хранить в каждом векторе указатель на последний не взятый товар.
Пока у нас не кончились деньги будем брать либо самый первый товар в векторе S, либо в векторе W.
Если самый дешевый товар дороже, имеющихся у нас денег, то заканчиваем.
За реализацией второй части алгоритма(где максимизируем товары типа S), смотри код.
Легко видеть, что при таком решении мы потратили минимальное количество денег, так как всегда брали самый дешевый товар из доступных, а это не хуже чем все остальные варианты.