← 返回题目列表

Codeforces · 1256/E

E. 又一个团队划分

中文机器翻译题面 查看原题

您的大学有 $$$n$$$ 名学生。第 $$$i$$$ 个学生的编程技能是 $$$a_i$$$。作为一名教练,你希望将他们分成几组,为即将到来的 ICPC 决赛做好准备。想象一下,如果这所大学有 $$$2 \cdot 10^5$$$ 学生准备好参加期末考试,那该多好啊!

每个团队应至少由三名学生组成。每个学生都应该属于一个团队。团队的多样性是属于该团队的某些学生的最大编程技能与属于该团队的某些学生的最小编程技能之间的差值(换句话说,如果该团队由具有编程技能 $$$a[i_1], a[i_2], \dots, a[i_k]$$$ 的 $$$k$$$ 学生组成,则该团队的多样性为 $$$\max\limits_{j=1}^{k} a[i_j] - \min\limits_{j=1}^{k} a[i_j]$$$)。

总多样性是组成的所有团队的多样性之和。

你的任务是最小化学生划分的总多样性,并找到划分学生的最佳方式。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 学生人数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个学生的编程技能。

输出

在第一行中打印两个整数 $$$res$$$ 和 $$$k$$$ — 学生所在部门的最小总多样性以及所在部门的团队数量。

在第二行中打印 $$$n$$$ 整数 $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_i \le k$$$),其中 $$$t_i$$$ 是第 $$$i$$$ 学生所属的团队编号。

如果有多个答案,您可以打印任何答案。请注意,您不需要最小化团队数量。每个团队应至少由三名学生组成。

示例

输入 #1

5
1 1 3 4 2

输出 #1

3 1
1 1 1 1 1

输入 #2

6
1 5 12 13 2 15

输出 #2

7 2
2 2 1 1 2 1

输入 #3

10
1 2 5 129 185 581 1041 1909 1580 8150

输出 #3

7486 3
3 3 3 2 2 2 2 1 1 1

注意

在第一个示例中,只有一个团队的技能为 $$$[1, 1, 2, 3, 4]$$$,因此答案为 $$$3$$$。可以证明你无法得到更好的答案。

在第二个示例中,有两个团队的技能分别为 $$$[1, 2, 5]$$$ 和 $$$[12, 13, 15]$$$,因此答案为 $$$4 + 3 = 7$$$。

在第三个示例中,有三支队伍的技能分别为 $$$[1, 2, 5]$$$、$$$[129, 185, 581, 1041]$$$ 和 $$$[1580, 1909, 8150]$$$,所以答案为 $$$4 + 912 + 6570 = 7486$$$。