hlbt和cpy都很贪婪(误)
hlbt大盗和cpy大盗意外获取了n桶泡面,它们可以放心地晚上开泡面party了!
为了不让有谁晚上高兴地吃泡面而另一个人眼馋,hlbt和cpy获得的泡面的数量之差的绝对值不能超过1。
然而每桶泡面的多少是不一样的,第i桶泡面质量为w[i]。
hlbt争不过cpy,但是他想知道他们各自获得泡面总质量之差尽可能小的情况下hlbt获得泡面总质量会比cpy少多少。
(争不过指hlbt的总质量会比cpy的少或者相等)
本题单个测试点内有多组测试数据。 本 题 单 个 测 试 点 内 有 多 组 测 试 数 据 。
输入的第一行是一个正整数 T,表示该测试点内数据组数。
对于每组测试数据的格式为:
每组测试数据占两行。
第一行是一个整数 n,表示泡面的个数。
第二行有 n 个整数,第 i 个整数表示第 i 桶泡面的质量 w[i] 。
对于每组数据输出一个数表示答案
2 3 2 2 4 4 1 2 3 6
0 2
第一组:hlbt拿第1、2桶泡面,cpy拿第3桶,答案为0;
第二组:hlbt拿第2、3桶泡面,cpy拿第1、4桶泡面,答案为2;
对于40%的数据,保证 w[i]<=1000
对于100%的数据, T<=20,n<=30,w[i]<=2^{30}