问题 1036. -- 分配宝藏

1036: 分配宝藏

时间限制:1000 ms 内存限制:128 MB
提交:692 解决:200
[ 提交][ 状态][ 讨论版]

题目描述

两个寻宝者找到一个宝藏，里面包含着n件物品，每件物品的价值是w[i]。suma代表寻宝者A所获物品的总价值，sumb代表寻宝者B所获物品的总价值，请问怎么分配，能使得|suma - sumb|（即suma与sumb之差的绝对值）最小。

输入

有多组输入数据，第一行为一个数字T，代表有T组输入数据 (0接下来为T组数据，每组数据分为两行：
第一行有一个整数n, 表示物品个数，其中0第二行有n个整数，第i个正数w[i]代表第i件物品的价值，其中0注意：所有数据均为正整数。

输出

一共T行。
对于每组数据，输出一个整数，表示|suma-sumb|。

样例输入

2 2 2 3 4 1 2 3 4

样例输出

1 0

提示

来源

2014西电ACM校赛现场赛

[ 提交][ 状态][ 讨论版]
Baidu
map