Тарифы
Оператор сотовой связи решил разработать несколько безлимитных тарифных планов, отличающихся между собой ежемесячной абонентской платой и набором дополнительных услуг. Менеджерам по работе с клиентами удалось выяснить, сколько каждый из VIP-абонентов компании готов тратить в месяц на услуги сотовой связи. Теперь сотовая компания хочет предложить каждому из абонентов свой тарифный план, но, к сожалению, комитет по антимонопольной политике разрешает сотовой компании иметь не более K безлимитных тарифных планов.
Помогите менеджерам компании разработать эти K тарифных планов, чтобы максимизировать доходы компании.
Формат входных данных
В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100).
Далее записано N целых чисел Ai — сумма, которую i-ый абонент готов тратить на связь в месяц (0≤Ai≤100000).
Формат выходных данных
Выведите в выходной файл K натуральных чисел — размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 10^9.
Считается, что каждому абоненту будет предложен тарифный план, в котором абонентская плата максимально возможная, но не превышающая Ai, и этот абонент будет обслуживаться по этому тарифному плану. Если такого тарифного плана не окажется, абонент не будет обслуживаться компанией.
Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.
Помогите менеджерам компании разработать эти K тарифных планов, чтобы максимизировать доходы компании.
Формат входных данных
В первой строке входного файла записаны два числа: количество VIP-абонентов компании N (1≤N≤100) и количество тарифных планов K (1≤K≤100).
Далее записано N целых чисел Ai — сумма, которую i-ый абонент готов тратить на связь в месяц (0≤Ai≤100000).
Формат выходных данных
Выведите в выходной файл K натуральных чисел — размеры абонентской платы в тарифных планах в порядке возрастания. Размер абонентской платы не должен быть меньше 1 и не может превышать 10^9.
Считается, что каждому абоненту будет предложен тарифный план, в котором абонентская плата максимально возможная, но не превышающая Ai, и этот абонент будет обслуживаться по этому тарифному плану. Если такого тарифного плана не окажется, абонент не будет обслуживаться компанией.
Доходы компании вычисляются как сумма абонентской платы, внесенной всеми абонентами компании.
Воспользуемся методом динамического программирования.
Заметим, что ежемесячная абонентская плата для тарифа не будет совпадать ни с одной суммой, которую готовы заплатить абоненты, только в том случае, если этим тарифом никто не пользуется. Действительно, пусть это не так. Тогда рассмотрим группу абонентов, пользующуюся этим тарифом. Поднимем абонентскую плату до минимального значения суммы, которую готовы заплатить эти абоненты. При этом заработок оператора сотовой связи увеличится, и никто из абонентов не поменяет тарифного плана.
Для решения задачи отсортируем клиентов по неубыванию суммы, которую они готовы тратить на связь в месяц, и запишем эти суммы в массив A. После этого проведём последовательное вычисление элементов массива Ans[i,j], в элементе с индексами i, j которого будет храниться максимальная сумма, которую может заработать компания при обслуживании первых i клиентов и использовании ровно j тарифных планов.
Как же вычислить Ans[i,j]? Воспользуемся вышеизложенным утверждением. Для каждого 1<=l<=i попробуем подключить абонентов A[i-l+1],…,A[i] к тарифному плану, абонентская плата которого, совпадает с той суммой, которую может заплатить A[i-l+1] абонент. Т.к. абоненты отсортированы по неубыванию суммы, которую они готовы тратить на сотовую связь, то всех перечисленных абонентов устроит этот тарифный план. Остаётся выбрать максимум по всем возможным l.
При инициализация массива Ans присвоим Ans[i,j] ноль, если i=j=0, и минус бесконечность иначе.
Не стоит забывать, что не может быть двух тарифных планов с одинаковой абонентской оплатой.
После подсчёта Ans[i,j] для всех возможных i и j, максимальная сумма, которую сможет заработать оператор, следует искать среди элементов Ans[N,1],…,Ans[N,K].
Ответ можно будет восстановить, если для каждого Ans[i,j] запоминать l, для которого прибыль была максимальна. Если в ответе получилось меньше чем K тарифов, то для оставшихся можно вывести любые числа, удовлетворяющие условиям.
Заметим, что ежемесячная абонентская плата для тарифа не будет совпадать ни с одной суммой, которую готовы заплатить абоненты, только в том случае, если этим тарифом никто не пользуется. Действительно, пусть это не так. Тогда рассмотрим группу абонентов, пользующуюся этим тарифом. Поднимем абонентскую плату до минимального значения суммы, которую готовы заплатить эти абоненты. При этом заработок оператора сотовой связи увеличится, и никто из абонентов не поменяет тарифного плана.
Для решения задачи отсортируем клиентов по неубыванию суммы, которую они готовы тратить на связь в месяц, и запишем эти суммы в массив A. После этого проведём последовательное вычисление элементов массива Ans[i,j], в элементе с индексами i, j которого будет храниться максимальная сумма, которую может заработать компания при обслуживании первых i клиентов и использовании ровно j тарифных планов.
Как же вычислить Ans[i,j]? Воспользуемся вышеизложенным утверждением. Для каждого 1<=l<=i попробуем подключить абонентов A[i-l+1],…,A[i] к тарифному плану, абонентская плата которого, совпадает с той суммой, которую может заплатить A[i-l+1] абонент. Т.к. абоненты отсортированы по неубыванию суммы, которую они готовы тратить на сотовую связь, то всех перечисленных абонентов устроит этот тарифный план. Остаётся выбрать максимум по всем возможным l.
При инициализация массива Ans присвоим Ans[i,j] ноль, если i=j=0, и минус бесконечность иначе.
Не стоит забывать, что не может быть двух тарифных планов с одинаковой абонентской оплатой.
После подсчёта Ans[i,j] для всех возможных i и j, максимальная сумма, которую сможет заработать оператор, следует искать среди элементов Ans[N,1],…,Ans[N,K].
Ответ можно будет восстановить, если для каждого Ans[i,j] запоминать l, для которого прибыль была максимальна. Если в ответе получилось меньше чем K тарифов, то для оставшихся можно вывести любые числа, удовлетворяющие условиям.
