← 返回题目

题库练习集合问题

← 上一题下一题 →

A71495 | $集合问题$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

有一组正整数，总数不超过 1000 ，其中最大值记为 M 。 现要将它们划分成 N 个集合，使得每个集合的元素之和与 M 的差的绝对值的和最小。 集合 A 中当前各元素之和记为 SUM(A) ，称为 A 的负荷； SUM(A) 与 M 之差的绝对值称为A的负荷与理想负荷的偏差，简称为A的偏差。 把这些整数划分成 N 个集合的方法是：按照从大到小的顺序，依次为每个整数分别选择一个集合； 确定一个整数所属集合时，先计算各集合的负荷，将该整数分配给负荷最小的那个集合。 求使得各集合的偏差之和最小的划分方案中，集合的数目 N 。如果这样的方案不止一种，则输出各方案中，集合数最大的那种方案的集合数 N 。

输入格式

共输入 K+1 个整数。其中第一个整数是 K 代表要划分的整数总数，后面依次是 K 个整数的值。 K 不超过 1000 。

输出格式

一个整数，代表集合数 N 。

输入输出样例

输入 #1

8
2 4 9 12 16 80 28 72

输出 #1

C++ 编辑器

输入

输出