#P18569. [ukiepc2026]Jammer Jam

[ukiepc2026]Jammer Jam

Jammer Jam

题目描述

游泳馆需要根据游泳者的速度将他们分配到泳道。

已知每位游泳者的独立游泳速度(米/小时)。同一泳道中的游泳者初始可以任意排列,但最终所有人都会追上泳道中速度最慢的人,并被迫与他保持相同的速度。

因此,一条泳道中每位游泳者最终的速度都等于该泳道中所有人的最低速度。

现在有 nn 名游泳者、ll 条泳道。你需要将所有游泳者分配到这些泳道中,且每条泳道至少分配一人,使所有游泳者最终速度的算术平均值最大。

请输出这个最大的平均速度,以及一种能够达到该最优值的分配方案。

图示(重绘示意图)

图 J.1:样例 3 的三条泳道,一条泳道中所有人最终均按最慢者的速度前进。

图 J.1:样例 3 的三条泳道,一条泳道中所有人最终均按最慢者的速度前进。 本图为重绘示意图。

输入格式

第一行输入两个整数 n,ln,l,分别表示游泳者数量和泳道数量。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 为第 ii 名游泳者的速度,单位为米/小时。

输出格式

第一行输出一个实数,表示所有游泳者最终速度的最大平均值。答案的绝对或相对误差不超过 10−610^{-6} 即可。

第二行输出 nn 个整数。第 ii 个整数表示第 ii 名游泳者被安排的泳道编号,编号在 11 到 ll 之间。每条泳道应至少使用一次。

如果存在多种最优分配方案,输出任意一种即可。

样例 #1

输入

3 2
100 200 50

输出(答案不唯一)

100
1 2 1

样例 #2

输入

4 2
11 22 34 47

输出(答案不唯一)

22.5
1 1 2 2

样例 #3

输入

10 3
34 123 127 161 168 30 44 150 183 193

输出(答案不唯一)

110.3
1 2 2 3 3 1 1 2 3 3

数据范围与保证

  • 1≤l≤n≤30001\le l\le n\le3000;
  • 1≤ai≤1061\le a_i\le10^6,所有速度均为整数。