P1599. 空间站平衡

ID: 600
远端评测题
1000ms
10MiB
尝试: 0
已通过: 0
难度: (无)
上传者: Hydro
标签>

题目描述

国际空间站的实验室中有许多离心机。每个离心机包含若干个（C个）舱室，每个舱室可容纳0、1或2个标本。你需要编写一个程序，将所有S个标本分配到舱室中（每个舱室最多放2个标本），并最小化以下“不平衡度”（IMBALANCE）表达式：

[
\text{IMBALANCE} = \sum_{i=1}^{C} | \text{CM}_i - \text{AM} |
]

其中：

• $\text{CM}_i$ 是第i个舱室的质量，等于该舱室中所有标本的质量之和。
• $\text{AM}$ 是舱室的平均质量，等于所有标本的总质量除以舱室数量C。

输入格式

输入包含多组数据。每组数据的第一行包含两个整数：第一个数（1 ≤ C ≤ 5）表示舱室数量，第二个数（1 ≤ S ≤ 2C）表示标本数量。第二行包含S个整数，表示每个标本的质量（1到1000之间），用空格分隔。

输出格式

对于每组输入，按以下格式输出：

1. 第一行：“Set #X”，其中X为当前组号（从1开始）。
2. 接下来C行：每行表示一个舱室的分配情况，格式为“ 舱室编号: 质量1 质量2”（舱室编号从0开始，质量之间用单个空格分隔，若舱室无标本则不输出质量）。
3. 再输出一行：“IMBALANCE = X”，其中X为计算出的不平衡度，保留5位小数。
4. 每组输出的最后加一个空行。

输入示例 1

2 3  
6 3 8  
3 5  
51 19 27 14 33  
5 9  
1 2 3 5 7 11 13 17 19  

输出示例 1

Set #1  
 0: 6 3  
 1: 8  
IMBALANCE = 1.00000  

Set #2  
 0: 51  
 1: 19 27  
 2: 14 33  
IMBALANCE = 6.00000  

Set #3  
 0: 1 17  
 1: 2 13  
 2: 3 11  
 3: 5 7  
 4: 19  
IMBALANCE = 11.60000  

来源

South Central USA 1996