🐷大肚肚
CF-81C3

分组

2.0s💾 256MB

📋 题目描述

现有 nn 个整数 t1,t2,...,tnt_1,t_2,...,t_n 请你将他们按照要求分成两组:第一组的数据个数为 aa ,第二组的数据个数为 bb ,第一组的平均数和第二组的平均数之和要越大越好。

📥 输入格式

第一行仅有一个整数 nn2n1052 ≤ n ≤ 10^5 ),第二行包含两个正整数 aabb1a,bn11 ≤ a, b ≤ n-1, a+b=na + b = n ),第三行包含一个整数序列 t1,t2,...,tnt_1,t_2,...,t_n1ti51\le t_i\le 5 )。

📤 输出格式

仅有一行,包含一个整数序列 f1,f2,...,fnf_1,f_2,...,f_n1fin1\le f_i \le n ),两两之间用一个空格分隔。如果 fi=1f_i=1 代表原序列中的第 ii 个数被分在第一组,如果 fi=2f_i=2 代表原序列中的第 ii 个数被分在第一组。如果有多个满足题意的解,则输出字典序最小那个解。

💡 提示

在第一个样本中,第一科目的平均分数为4,而第二个样本的平均分数为4.5。总平均分为8.5。

📝 样例 1

输入
5
3 2
4 4 5 4 4
输出
1 1 2 1 2

📝 样例 2

输入
4
2 2
3 5 4 5
输出
1 1 2 2

📝 样例 3

输入
6
1 5
4 4 4 5 4 4
输出
2 2 2 1 2 2

💡 题目讲解

1

理解题意

nn 个数分成两组:第一组 aa 个,第二组 bb 个。a+b=na+b=n

目标:第一组平均数 + 第二组平均数 尽量大


设第一组数的和为 S1S_1,总数为 SS。第二组和为 SS1S-S_1

目标 =S1a+SS1b=S1(1a1b)+Sb= \frac{S_1}{a} + \frac{S-S_1}{b} = S_1 \cdot (\frac{1}{a} - \frac{1}{b}) + \frac{S}{b}

如果 a<ba < b1a1b>0\frac{1}{a} - \frac{1}{b} > 0S1S_1 越大越好 → 第一组拿最大的 aa 个数

如果 a>ba > b1a1b<0\frac{1}{a} - \frac{1}{b} < 0S1S_1 越小越好 → 第一组拿最小的 aa 个数

排序,按极端取。

1 / 5