45. Оптимальные пороги

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

Один из подходов к оптимизации сервисирования клиентов основан на введении бюджетных порогов — требований к минимальной величине ожидаемых ежемесячных расходов (далее, ОЕР) клиента на услуги компании, необходимых для отнесения к определённой категории. При таком подходе для каждого клиента подбирается категория обслуживания с максимально возможным порогом, не превышающим величину ОЕР. Если величина ОЕР клиента ниже бюджетного порога по каждой из категорий, клиент считается самосервисируемым (не относящимся ни к одной категории).

Подбирать бюджетные пороги для различных категорий обслуживания будем с помощью целевой метрики, значение которой равно сумме бюджетных порогов всех клиентов. Экономический смысл данной метрики основан на следующем предположении: при отнесении к некоторой категории клиент гарантированно потратит на услуги компании величину, равную бюджетному порогу данной категории. Сумму этих «гарантированных трат» и будем максимизировать.

Более формально, пусть $N$ — общее количество клиентов компании, $A_i$ — величина ОЕР $i$-го клиента $(1 \leqslant i \leqslant N)$.

Зафиксируем бюджетные пороги $B_1 \lt B_2 \lt \ldots \lt B_K$ и введём функцию $T$ — кусочно-постоянную неубывающую функцию, возвращающую бюджетный порог для величины ОЕР, равной $a$: $$T(a) = \begin{cases} 0, \qquad \hspace{0.5em} a \lt B_1, \\\\ B_1 \qquad B_1 \leqslant a \lt B_2, \\\\ B_2 \qquad B_2 \leqslant a \lt B_3, \\\\ \ldots \\\\ B_K \qquad a \geqslant B_K. \end{cases}$$

Тогда задачу оптимизации можно сформулировать следующим образом:

при условии, что количество категорий сервисирования фиксировано и равно $K$.

Первая строка содержит два числа, записанных через пробел: количество клиентов компании $N$ $(1 \leqslant N \leqslant 100)$ и категорий сервисирования $K$ $(1 \leqslant K \leqslant 100)$.

Вторая строка содержит $N$ целых чисел $A_i$ $(0 \leqslant A_i \leqslant 100000)$ — величины ОЕР клиентов на услуги компании, тыс. руб.

Выведите $K$ натуральных чисел — оптимальные бюджетные пороги $B_j$ $(1 \leqslant j \leqslant K)$ в порядке возрастания на одной строке через пробел.

• Клиент с ОЕР 1 тыс. — самосервисируемый.
• Клиенты с ОЕР 3 тыс. и 4 тыс. распределяются в категорию с бюджетным порогом 3 тыс.
• Клиент с ОЕР 5 тыс. выделяется в отдельную категорию.
• Клиенты с ОЕР 10 тыс. и 12 тыс. распределяются в категорию с порогом 10 тыс.
• Клиент с ОЕР 80 тыс. выделяется в отдельную категорию.

Значение целевой метрики составит:

Каждый клиент попадает в отдельную категорию с бюджетным порогом, равным ОЕР. В четвёртую категорию не попадает ни одного клиента.

Клиенты с ОЕР, равными 0, 4 тыс. и 2 тыс., являются самосервисируемыми. Остальные клиенты распределяются в единственную категорию с бюджетным порогом 6 тыс.

Значение целевой метрики составит: $T(0) + T(4) + T(2) + T(8) + T(17) + T(6) = 0 + 0 + 0 + 6 + 6 + 6 = 18$.