问题 AA: 牛马运动会
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：76
解决：19
题目描述
牛马协会正在筹备一场接力赛。
协会里有m个牛马，他们将在比赛中一个接一个地跑，牛马i的速度是si。
第 i 阶段的差值 di 为前 i 个牛马的跑速最大值与最小值之差。
如果ai表示第i位上场的牛马的速度，也就是
di=max(a1,a2,…,ai)−min(a1,a2,…,ai)。
你想要最小化差值d1+d2+...+dn的总和。
为此，您可以更改牛马们上场的顺序。可以实现的最小可能的总和是多少?
协会里有m个牛马，他们将在比赛中一个接一个地跑，牛马i的速度是si。
第 i 阶段的差值 di 为前 i 个牛马的跑速最大值与最小值之差。
如果ai表示第i位上场的牛马的速度，也就是
di=max(a1,a2,…,ai)−min(a1,a2,…,ai)。
你想要最小化差值d1+d2+...+dn的总和。
为此，您可以更改牛马们上场的顺序。可以实现的最小可能的总和是多少?
输入
第一行输入一个整数n(1≤n≤2000)，代表牛马协会中牛马的个数
第二行输入n个整数s1, s2, ... , sn(1≤si≤109)，代表牛马们跑步的速度
第二行输入n个整数s1, s2, ... , sn(1≤si≤109)，代表牛马们跑步的速度
输出
输出一个整数，代表选择上场顺序后，可以实现的最小的差值总和。
样例输入 复制
3
3 1 2样例输出 复制
3提示
在第一个样例中，我们可以先选择第三个牛马，然后选择第一个牛马，最后选择第二个牛马。
d1=max(2)−min(2)=2−2=0.
d2=max(2,3)−min(2,3)=3−2=1.
d3=max(2,3,1)−min(2,3,1)=3−1=2.
结果为d1+d2+d3=0+1+2=3 ，
可以证明，不可能实现更小的值。
在第二个测试用例中，唯一可能的顺序就是d1=0，所以结果为0.
d1=max(2)−min(2)=2−2=0.
d2=max(2,3)−min(2,3)=3−2=1.
d3=max(2,3,1)−min(2,3,1)=3−1=2.
结果为d1+d2+d3=0+1+2=3 ，
可以证明，不可能实现更小的值。
在第二个测试用例中，唯一可能的顺序就是d1=0，所以结果为0.