#8911. 集合问题 普及/提高−

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

有一组正整数,总数不超过 ,其中最大值记为 。现要将它们划分成 个集合,使得每个集合的元素之和与M的差的绝对值的和最小。 集合

当前各元素之和记为 ,称为 的负荷 之差的绝对值称为 的负荷与理想负荷的偏差,简称为 的偏差。把这些整数划分

成N个集合的方法是:按照从大到小的顺序,依次为每个整数分别选择一个集合;确定一个整数所属集合时,先计算各集合的负荷,将该整数分配给负荷最小的那个集合。

求使得各集合的偏差之和最小的划分方案中,集合的数目 。如果这样的方案不止一种,则输出各方案中,集合数最大的那种方案的集合数

输入格式

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

输出格式

一个整数,代表集合数

样例

样例输入

8
2 4 9
12 16
80 28
72

样例输出

3