@Restars

Помогите пожалуйста решить задачу
Домино
Вася установил на телефон игру, где в каждой клетке полоски размером 2×N записано целое число. Цель игры состоит в том, чтобы накрыть часть клеток доминошками размерами 2×1 так, чтобы сумма чисел на не покрытых доминошками клетках была минимальной.

Доминошки можно поворачивать горизонтально или вертикально, они не могут накладываться. Обязательно использовать все имеющиеся доминошки.

Формат входных данных
В первой строке вводится два числа N и K (1 ≤ N ≤ 2×105, 0 ≤ K ≤ 2×105, 0 ≤ N × K ≤ 2 × 105, N ≥ K) — размер полоски и количество имеющихся доминошек.

В следующих N строках вводятся по 2 целых числа, записанных на полоске. Числа не превосходят 109 по модулю.

Формат результата
Выведите N строк по 2 числа в каждой — описание расположения доминошек на полоске. Каждая клетка должна описываться либо числом от 1 до K — номером доминошки, которой она накрыта, либо числом 0, в случае, если она не накрыта доминошкой.

Если ответов несколько — выведите любой из них.

0

@dondublon

Интересная задачка. Думаю, жадный алгоритм поможет.
Доску с числами можно представить в виде конечного числа пар клеток, которые можно покрыть костяшками. Пары, разумеется, пересекаются. Вертикальных пар N, горизонтальных что-то вроде 2*(N-1). (Проверить!). У каждой пары есть своя сумма. Их надо собрать в структуру. Для простоты можно список, но для быстродействия желательно не просто список, а ввести какие-то указатели - чтобы по индексу клетки найти все пары, в которые она входит.
На каждой итерации покрываем пару с максимальной суммой - из оставшихся непомеченными. Помечаем "накрытые", чтобы туда не пытаться ставить - в нашей структуре. Каждое выставление костяшки помечает более одной пары клеток.
Повторяем, пока не кончатся костяшки. Bingo!

1

@Restars

Спасибо за наводку!

0

@pshpis

Не хорошо списывать Высшую Пробу))) Это решение естественно не работает, так как вы отсекается таким образом множество других вариантов и не выбираете как лучше отсечь. Есть контертест на котором это решение вообще упадет

0

@dondublon

pshpis, не понял, поясните, плз.
Я уверен на 99% Допускаю на 1%, что жадный алгоритм тут не пойдёт, всё-таки я не так вдумчиво анализировал задачу, чтобы дать 100% гарантии.
Почему решение упадёт - тем более непонятно. Я бы понял, если бы в каком-то случае оно было неверным (приведите конрпример, плз) но упасть - - -

0

@Miryz

dondublon, 3 доминошки
10 5
7 9
3 9
3 3

0

@dondublon

Miryz, маньяк.

0

@Miryz

dondublon, ну просто меня тоже интересует решение данной задачи.

0