问一道题 、、

回复帖子

@Inkyo墨攸 2020-05-23 14:25 回复

题意大概是这样的:

给你 $N$ 个数,你需要把这 $N$ 个数分成两组,使两个组中的数的和 的差值最小(好绕啊)

要求复杂度为$O(n)$

请问洛谷上有这道题吗,如果没有能告诉我一下做法吗qwq

想了半天只糊了个 $O(n^2)$的

@Alan_Zhao  2020-05-23 14:28 回复 举报

在百度上就能搜到……是一个01背包,从这 $n$ 个数中选数,使得选的数的和最大且不超过 $\dfrac{sum}{2}$。

@Alan_Zhao  2020-05-23 14:37 回复 举报

@Inkyo墨攸 那我就没辙了。。。

说句闲话:实名羡慕你们这些有校内模拟赛的,我在弱市弱校,OIer都没几个。。。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。