USACO2014JAN 铜组第三题

题目描述
今年，农夫约翰（Farmer John）有 12 头牛参加参加冬季摩lympic（Moolympic）运动会，每头牛的技能水平是介于 1 到 1,000,000 之间的整数。

农夫约翰想把它们分成 4 支队伍，每支队伍 3 头牛，使得这些队伍在“总技能水平”方面尽可能“平衡”（一支队伍的技能水平是该队伍中所有牛的技能水平之和 ）。具体来说，他希望最小化 ( S - s )，其中 ( S ) 和 ( s ) 分别是各队伍技能水平的最大值和最小值。这样就能让技能水平最高的队伍和技能水平最低的队伍之间的差距尽可能小。

请帮助农夫约翰确定 ( S - s ) 可能的最小值。

问题名称：bteams

输入格式

• 第 1 至 12 行：每行包含一头牛的技能水平。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12

输出格式

• 第 1 行：( S - s ) 可能的最小值。

样例输出

1

输出详情
一种可行的分组方案是：(12, 1, 7)、(9, 8, 3)、(10, 5, 4)、(11, 2, 6) 。前两支队伍的技能总和是 20，后两支队伍的技能总和是 19，此时 ( S - s = 20 - 19 = 1 ) 。