问题 J: 分割队伍

---

【题目描述】

题目描述
有n个人正在排队办理业务，其中第i个人办理业务所需时间为ai。现在有两个窗口开放办理该业务，为了防止排队时间过长，你可以将这n个人按给定顺序分成两个队伍，例如从第i个人处将队列分割，意味着将第1至第i−1个人分为第一列，第i至第n个人分至第二个队伍，且不允许有一个队伍为空。
请问，如何分割这个队伍，能够使得得到的两个队列的总等待时间相差最小？
输入格式
输入共两行：
第一行，一个正整数n
第二行，n个正整数a1,a2,…,an
输出格式
输出分割后两个队伍等待时间差值的最小值。
数据范围
对于30%的数据，1≤n≤100
对于70%的数据，1≤n≤1000
对于100%的数据，1≤n≤100000，1≤ai≤10000
样例数据
输入:
3
1 1 100
输出:
98
说明:
第2和第3个人之间分割，前两个人的等待时间为2，最后那个人的等待时间为100，则两队列等待时间相差98。
输入:
6
1 2 3 4 5 6
输出:
1
说明:
第4和第5个人之间分割，前四个人的等待时间为10，后两个人的等待时间为11，则两队列等待时间相差1。
 

题目类型~

三星挑战赛 语言基础 

咻咻~

提交答案 状态 返回作业