Выходные данные

Входные данные

Новогодняя елка

Выходные данные

Первая и единственная строка выходного файла должна содержать одно целое число S – размер максимальной выгоды в монетах, которую может получить Аркадий Павлович.

input.txt	output.txt	Пояснение
2 3 1 1 3 3 3		Аркадий Павлович купит компьютеры у 1-го и 2-го продавцов и продаст их любым двум покупателям.
6 5 5 10 8 4 7 2 3 1 11 18 9		Наиболее выгодно купить компьютеры у 1-го, 4-го и 6-го продавцов и продать 3-ему, 4-ому и 5-ому покупателям.

Так повелось, что в Байтландии елки украшаются только новогодними одноцветными шарами. В связи с этим знаменитой компании по производству декоративных украшений «Yellow Toys» было поручено важное и ответственное задание – украшение главной новогодней елки страны.

Сотрудникам компании был составлен строгий перечень имеющихся новогодних игрушек (шаров), согласно которому в наличии имеется N одноцветных шаров, диметр i -го шара (1 ≤ i ≤ N) равен D_i миллиметров. Сотрудникам известно, что согласно национальным стандартам главная елка страны должны быть украшена не менее чем K шарами. Также стандарты четко регламентируют понятие показатель некрасивости – равный максимально возможному числу D^’_i – D’_j при 1 ≤ i, j ≤ M, где M – количество игрушек на елке, а D^’_i – их диаметр. Для приведенного ниже примера показатель некрасивости равен 21 – 16 = 5.

Рисунок №1.Описание второго примера, N = 6, K = 4, M = 4.

Ваша задача помочь сотрудникам компании из имеющихся N игрушек, выбрать M
(M ≥ K) игрушек так, чтобы для набора выбранных M шаров показатель некрасивости был минимальным.

Первая строка входного файла содержит два натуральных числа, разделенных одиночным пробелом N (2 ≤ N ≤ 100 000) и K (2 ≤ K ≤N) соответственно.

Вторая строка входного файла содержит ровно N целых чисел D_i (1 ≤ D_i ≤10⁹) – диаметр i -й новогодней игрушки (шара). Числа разделены одиночными пробелами. Игрушки нумеруются последовательно, в порядке их ввода, начиная с единицы.

Первая строка выходного файла должна содержать одно целое число M (K ≤ M ≤ N) – количество игрушек на елке.

Вторая строка выходного файла должна описывать набор выбранных для украшения елки игрушек и содержать M целых чисел Z_i (1 ≤ Z_i ≤ N, Z_i ≠ Z_j, если i ≠ j) – номера выбранных для украшения игрушек. Числа должны быть разделены одиночными пробелами. Если решений несколько, то выведите любое из них.

input.txt	output.txt
3 2 1 3 7	1 2
6 4 21 12 17 28 16 21	1 5 3 6
8 5 10 10 10 10 20 20 20 20	3 5 6 4 7 8

Ограничения:

Входной файл	input.txt
Выходной файл	output.txt
Время на тест	1 сек
Ограничение памяти	128 MB
Частичная оценка	N ≤ 20 – не менее 20 баллов
K = N, 20 < N ≤ 100 000 – не менее 15 баллов
K = N - 1, 20 < N ≤ 1000 - не менее 15 баллов
K = N - 2, 20 < N ≤ 200 - не менее 10 баллов
K < N - 2, 20 < N ≤ 1000 - не менее 15 баллов

Дата добавления: 2017-01-13