🐷大肚肚
CF-81C3

分组

⏱ 2.0s💾 256MB

📋 题目描述

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

📥 输入格式

第一行仅有一个整数 nn( 2≤n≤1052 ≤ n ≤ 10^5 ),第二行包含两个正整数 aa 和 bb( 1≤a,b≤n−11 ≤ a, b ≤ n-1, a+b=na + b = n ),第三行包含一个整数序列 t1,t2,...,tnt_1,t_2,...,t_n ( 1≤ti≤51\le t_i\le 5 )。

📤 输出格式

仅有一行,包含一个整数序列 f1,f2,...,fnf_1,f_2,...,f_n ( 1≤fi≤n1\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。第二组和为 S−S1S-S_1。

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

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

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

排序,按极端取。

1 / 5