Yet Another Division Into Teams

题意翻译

### 题目描述 你的大学里面有 $n$ 个学生，第 $i$ 个学生的水平为 $a_i$。作为一名教练，你想把他们分成若干个队伍已准备即将到来的 ICPC 决赛。 每一支队伍至少要有三名学生，并且每一位学生恰好属于一支队伍。定义一支队伍的极差为所有这支队伍的学生中水平最高的与最低的的水平之差。形式化的说，如果一支队伍中有 $k$ 个学生，水平分别为 $a_{i_1},a_{i_2},\cdots,a_{i_n}$，那么这支队伍的极差为 $\max\limits_{j=1}^{k}a_{i_j}-\min\limits_{j=1}^{k}a_{i_j}$。 总共的极差为所有队伍的极差之和。 你需要找到一种最优的分组方案使得总共的极差最小。 ### 输入格式 第一行一个整数 $n(1\leq n\leq 2\times 10^5)$ ，表示学生的人数。 第二行$n$个整数 $a_1,a_2,\cdots,a_n(1\leq a_i\leq 10^9)$，其中 $a_i$ 表示第 $i$ 个学生的水平。 ### 输出格式 第一行两个整数 $res,k$，表示最小的总共的极差以及最优方案中队伍的个数。 第二行 $n$ 个整数 $t_1,t_2,\cdots t_n(1\leq t_i\leq k)$，其中 $t_i$ 是第 $i$ 个学生所属的队伍编号。 如果有多种答案，你可以输出任意一个。注意到你不必最小化队伍的数量。每支队伍至少要有三个学生。 Translated By Karry5307

题目描述

There are $ n $ students at your university. The programming skill of the $ i $ -th student is $ a_i $ . As a coach, you want to divide them into teams to prepare them for the upcoming ICPC finals. Just imagine how good this university is if it has $ 2 \cdot 10^5 $ students ready for the finals! Each team should consist of at least three students. Each student should belong to exactly one team. The diversity of a team is the difference between the maximum programming skill of some student that belongs to this team and the minimum programming skill of some student that belongs to this team (in other words, if the team consists of $ k $ students with programming skills $ a[i_1], a[i_2], \dots, a[i_k] $ , then the diversity of this team is $ \max\limits_{j=1}^{k} a[i_j] - \min\limits_{j=1}^{k} a[i_j] $ ). The total diversity is the sum of diversities of all teams formed. Your task is to minimize the total diversity of the division of students and find the optimal way to divide the students.

输入输出格式

输入格式

The first line of the input contains one integer $ n $ ( $ 3 \le n \le 2 \cdot 10^5 $ ) — the number of students. The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ), where $ a_i $ is the programming skill of the $ i $ -th student.

输出格式

In the first line print two integers $ res $ and $ k $ — the minimum total diversity of the division of students and the number of teams in your division, correspondingly. In the second line print $ n $ integers $ t_1, t_2, \dots, t_n $ ( $ 1 \le t_i \le k $ ), where $ t_i $ is the number of team to which the $ i $ -th student belong. If there are multiple answers, you can print any. Note that you don't need to minimize the number of teams. Each team should consist of at least three students.

输入输出样例

输入样例 #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 

说明

In the first example, there is only one team with skills $ [1, 1, 2, 3, 4] $ so the answer is $ 3 $ . It can be shown that you cannot achieve a better answer. In the second example, there are two teams with skills $ [1, 2, 5] $ and $ [12, 13, 15] $ so the answer is $ 4 + 3 = 7 $ . In the third example, there are three teams with skills $ [1, 2, 5] $ , $ [129, 185, 581, 1041] $ and $ [1580, 1909, 8150] $ so the answer is $ 4 + 912 + 6570 = 7486 $ .