问一题，30分钟做完# JobHunting - 待字闺中
j*d
1 楼
给你一个数组，有偶数个数，要分成2个数组，每个数组所含的数的个数一样。要求两
数组和的差最小。
以为是背包，后来发现，无法得到2个equal size的数组。如何解决？除了greedy。
数组和的差最小。
以为是背包，后来发现，无法得到2个equal size的数组。如何解决？除了greedy。
a*k
2 楼
dfs
P*r
3 楼
咋做？想不出来啊。。
: dfs
【在 a****k 的大作中提到】
: dfs
: dfs
【在 a****k 的大作中提到】
: dfs
j*d
4 楼
难道不会MLE。
【在 a****k 的大作中提到】
: dfs
【在 a****k 的大作中提到】
: dfs
n*n
5 楼
排序吧。
h*1
6 楼
排序+ greedy
【在 j*****d 的大作中提到】
: 给你一个数组，有偶数个数，要分成2个数组，每个数组所含的数的个数一样。要求两
: 数组和的差最小。
: 以为是背包，后来发现，无法得到2个equal size的数组。如何解决？除了greedy。
【在 j*****d 的大作中提到】
: 给你一个数组，有偶数个数，要分成2个数组，每个数组所含的数的个数一样。要求两
: 数组和的差最小。
: 以为是背包，后来发现，无法得到2个equal size的数组。如何解决？除了greedy。
d*n
7 楼
我记得这个题是某次lc周赛的原题
隐约记得是二分找
具体的得再想想
隐约记得是二分找
具体的得再想想
u*d
8 楼
还是背包DP解：https://www.geeksforgeeks.org/partition-a-set-into-two-subsets
-such-that-the-difference-of-subset-sums-is-minimum/
-such-that-the-difference-of-subset-sums-is-minimum/
a*a
9 楼
sort in reverse order, then do dfs with pruning (early return if sum is
worse than current best result).
【在 j*****d 的大作中提到】
: 给你一个数组，有偶数个数，要分成2个数组，每个数组所含的数的个数一样。要求两
: 数组和的差最小。
: 以为是背包，后来发现，无法得到2个equal size的数组。如何解决？除了greedy。
p*r
10 楼
凭俺猪一样的智商，
目前想到只有是暴力dfs往下撸，
设一个min difference = max作为初始，
然后dfs往下撸，
不到n/2，就比min大的咔嚓掉
到了n/2, 更新min
目前想到只有是暴力dfs往下撸，
设一个min difference = max作为初始，
然后dfs往下撸，
不到n/2，就比min大的咔嚓掉
到了n/2, 更新min
p*r
11 楼
为啥要sort
【在 a****a 的大作中提到】
:
: sort in reverse order, then do dfs with pruning (early return if sum is
: worse than current best result).
【在 a****a 的大作中提到】
:
: sort in reverse order, then do dfs with pruning (early return if sum is
: worse than current best result).
p*r
12 楼
感觉上这个是对的，但是理论上没法证明。
【在 h***1 的大作中提到】
: 排序+ greedy
【在 h***1 的大作中提到】
: 排序+ greedy
j*d
13 楼
我突然觉得，背包就可以做，只是，boolean[] 变成 Node【】。 node里面，2个field
，reachable 一个boolean量。num 一个int，记录和为这个数的时候，用的个数？
，reachable 一个boolean量。num 一个int，记录和为这个数的时候，用的个数？
h*1
14 楼
先看看4个教怎样选的理论，然后extend到 6，8，．．．
【在 p**r 的大作中提到】
: 感觉上这个是对的，但是理论上没法证明。
【在 p**r 的大作中提到】
: 感觉上这个是对的，但是理论上没法证明。
n*g
15 楼
一个标准np hard.. 学名叫partition problem
但是易dp解
https://en.wikipedia.org/wiki/Partition_problem
但是易dp解
https://en.wikipedia.org/wiki/Partition_problem
n*g
16 楼
回头看了一眼上面的回复..
菜是有原因的.
菜是有原因的.
l*r
17 楼
先排序，然后a_1,a_2,...,a_(2n-1),a_(2n)
分组
a_1,a_(2n),a_3,a_(2n-2),...
a_2,a_(2n-1),a_4,a_(2n-3),...
当n=2是可以证明
a3 + a4 - a1 - a2 >= a1 + a4 - a2 - a3 >= a1 + a2 - a3 - a4
a4 + a2 - a1 - a3 >= a1 + a4 - a2 - a3 >= a1 + a3 - a2 - a4
所以abs(a1 + a4 - a2 - a3) <= abs(a3 + a4 - a1 - a2)
abs(a1 + a4 - a2 - a3) <= abs(a2 + a4 - a1 - a3)
如果n>=4，假设交换a_i，a_j （a_i with + sign and a_j with - sign with a_i <=
a_j).
so a_(2n-i + 1) >= a_(2n-j+1)
a_(2n-i+1) + a_j - a_i -a_(2n-j+1) >= a_(2n-i+1) + a_i - a_(2n-j+1) - a_j >=
a_i + a_(2n-j+1) - a_j - a_(2n-i+1)
如果a_i>=a_j,则a_(2n - i + 1) <= a_(2n-j + 1)
a_(2n-i+1) + a_j - a_i -a_(2n-j+1) <= a_(2n-i+1) + a_i - a_(2n-j+1) - a_j <=
a_i + a_(2n-j+1) - a_j - a_(2n-i+1)
所以任意交换两项都会让absolute diff变大。
这个分组是最佳的。
【在 j*****d 的大作中提到】
: 给你一个数组，有偶数个数，要分成2个数组，每个数组所含的数的个数一样。要求两
: 数组和的差最小。
: 以为是背包，后来发现，无法得到2个equal size的数组。如何解决？除了greedy。
分组
a_1,a_(2n),a_3,a_(2n-2),...
a_2,a_(2n-1),a_4,a_(2n-3),...
当n=2是可以证明
a3 + a4 - a1 - a2 >= a1 + a4 - a2 - a3 >= a1 + a2 - a3 - a4
a4 + a2 - a1 - a3 >= a1 + a4 - a2 - a3 >= a1 + a3 - a2 - a4
所以abs(a1 + a4 - a2 - a3) <= abs(a3 + a4 - a1 - a2)
abs(a1 + a4 - a2 - a3) <= abs(a2 + a4 - a1 - a3)
如果n>=4，假设交换a_i，a_j （a_i with + sign and a_j with - sign with a_i <=
a_j).
so a_(2n-i + 1) >= a_(2n-j+1)
a_(2n-i+1) + a_j - a_i -a_(2n-j+1) >= a_(2n-i+1) + a_i - a_(2n-j+1) - a_j >=
a_i + a_(2n-j+1) - a_j - a_(2n-i+1)
如果a_i>=a_j,则a_(2n - i + 1) <= a_(2n-j + 1)
a_(2n-i+1) + a_j - a_i -a_(2n-j+1) <= a_(2n-i+1) + a_i - a_(2n-j+1) - a_j <=
a_i + a_(2n-j+1) - a_j - a_(2n-i+1)
所以任意交换两项都会让absolute diff变大。
这个分组是最佳的。
【在 j*****d 的大作中提到】
: 给你一个数组，有偶数个数，要分成2个数组，每个数组所含的数的个数一样。要求两
: 数组和的差最小。
: 以为是背包，后来发现，无法得到2个equal size的数组。如何解决？除了greedy。
n*e
18 楼
不错
<=
【在 l******r 的大作中提到】
: 先排序，然后a_1,a_2,...,a_(2n-1),a_(2n)
: 分组
: a_1,a_(2n),a_3,a_(2n-2),...
: a_2,a_(2n-1),a_4,a_(2n-3),...
: 当n=2是可以证明
: a3 + a4 - a1 - a2 >= a1 + a4 - a2 - a3 >= a1 + a2 - a3 - a4
: a4 + a2 - a1 - a3 >= a1 + a4 - a2 - a3 >= a1 + a3 - a2 - a4
: 所以abs(a1 + a4 - a2 - a3) <= abs(a3 + a4 - a1 - a2)
: abs(a1 + a4 - a2 - a3) <= abs(a2 + a4 - a1 - a3)
: 如果n>=4，假设交换a_i，a_j （a_i with + sign and a_j with - sign with a_i <=
<=
【在 l******r 的大作中提到】
: 先排序，然后a_1,a_2,...,a_(2n-1),a_(2n)
: 分组
: a_1,a_(2n),a_3,a_(2n-2),...
: a_2,a_(2n-1),a_4,a_(2n-3),...
: 当n=2是可以证明
: a3 + a4 - a1 - a2 >= a1 + a4 - a2 - a3 >= a1 + a2 - a3 - a4
: a4 + a2 - a1 - a3 >= a1 + a4 - a2 - a3 >= a1 + a3 - a2 - a4
: 所以abs(a1 + a4 - a2 - a3) <= abs(a3 + a4 - a1 - a2)
: abs(a1 + a4 - a2 - a3) <= abs(a2 + a4 - a1 - a3)
: 如果n>=4，假设交换a_i，a_j （a_i with + sign and a_j with - sign with a_i <=
l*m
19 楼
如果同时交换两个元素呢？因为两个元素的和可能导致更细的粒度
：先排序，然后a_1,a_2,...,a_(2n-1),a_(2n)
：分组
：先排序，然后a_1,a_2,...,a_(2n-1),a_(2n)
：分组
w*d
20 楼
不对吧，假如是1,2,3,4,5,100。最好分组难道不是1,2,100和3,4,5？
<=
【在 l******r 的大作中提到】
: 先排序，然后a_1,a_2,...,a_(2n-1),a_(2n)
: 分组
: a_1,a_(2n),a_3,a_(2n-2),...
: a_2,a_(2n-1),a_4,a_(2n-3),...
: 当n=2是可以证明
: a3 + a4 - a1 - a2 >= a1 + a4 - a2 - a3 >= a1 + a2 - a3 - a4
: a4 + a2 - a1 - a3 >= a1 + a4 - a2 - a3 >= a1 + a3 - a2 - a4
: 所以abs(a1 + a4 - a2 - a3) <= abs(a3 + a4 - a1 - a2)
: abs(a1 + a4 - a2 - a3) <= abs(a2 + a4 - a1 - a3)
: 如果n>=4，假设交换a_i，a_j （a_i with + sign and a_j with - sign with a_i <=
<=
【在 l******r 的大作中提到】
: 先排序，然后a_1,a_2,...,a_(2n-1),a_(2n)
: 分组
: a_1,a_(2n),a_3,a_(2n-2),...
: a_2,a_(2n-1),a_4,a_(2n-3),...
: 当n=2是可以证明
: a3 + a4 - a1 - a2 >= a1 + a4 - a2 - a3 >= a1 + a2 - a3 - a4
: a4 + a2 - a1 - a3 >= a1 + a4 - a2 - a3 >= a1 + a3 - a2 - a4
: 所以abs(a1 + a4 - a2 - a3) <= abs(a3 + a4 - a1 - a2)
: abs(a1 + a4 - a2 - a3) <= abs(a2 + a4 - a1 - a3)
: 如果n>=4，假设交换a_i，a_j （a_i with + sign and a_j with - sign with a_i <=
w*d
21 楼
最好的解法还是DP吧。假设F(k, n, m)表示在1到m个元素中和离k最近的n个元素，那原
题就是求F(sum/2, n/2, n)。递推公式就是 F(k, n, m) = better{F(k-x_m, n-1, m-1
), F(k, n, m-1)}。最后复杂度是 sum * n^2， 是pseudo-polynomia。如果整数都有
bound，那就是n^3。
题就是求F(sum/2, n/2, n)。递推公式就是 F(k, n, m) = better{F(k-x_m, n-1, m-1
), F(k, n, m-1)}。最后复杂度是 sum * n^2， 是pseudo-polynomia。如果整数都有
bound，那就是n^3。
相关阅读
请问有H1b申请的微信群吗?求Splunk实习内推U家Bonus出来了先在毕业进flg的小孩眼戒太窄了，还谁都看不起。劝你们一句话：世界是多维的猎头要跟我skype视频，我应该穿什么衣服？对于PhD new grad，offer expectation在多少比较合适啊？请问有没有人了解GMO这家公司 (转载)你经历过各类奇葩面试如果opt-extension申请并通过，但原来12月的OPT 还没过期的话，能在不 E-verify的公司工作吗？有没有在工业界工作周围大都是外国人的id我发誓从今天开始，绝不加班，一个小时都不， (转载)【GS内推】统计，分控，报表职位Northwindsor Corp 可信吗Two CFD Developer Positions at Altair要不要接这个offer ? (有戏剧性)帮人找工作的公司组里招人@HPE在美国华人干不过阿三是因为 (转载)5月份毕业OPT7月生效。中间算身份断档吗？问个面试常见的问题，希望各位有经验的帮忙想想怎么回答