问一道题、、

学术版

Inkyo @ 2020-05-23 14:25:03

题意大概是这样的：

给你 N 个数，你需要把这 N 个数分成两组，使两个组中的数的和的差值最小（好绕啊）

要求复杂度为O(n)

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

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

by cxqghzj @ 2020-05-23 14:26:03

给题链接

by Inkyo @ 2020-05-23 14:26:54

@cxqghzj 没有，模拟赛做的题

by cxqghzj @ 2020-05-23 14:27:14

。。。

by cxqghzj @ 2020-05-23 14:27:39

直接模拟

by Nathaly @ 2020-05-23 14:28:16

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

by Nathaly @ 2020-05-23 14:28:42

@Inkyo墨攸

by Inkyo @ 2020-05-23 14:29:58

@Alan_Zhao

啊这

我设计的01背包只能跑 O(n^2)

by Nathaly @ 2020-05-23 14:31:32

@Inkyo墨攸是 O(n\times \text{值域}) 吧，但你也没说值域啊

by Inkyo @ 2020-05-23 14:32:47

@Alan_Zhao 但是 n 是 10^6 级别的，乘个值域会炸

by Nathaly @ 2020-05-23 14:37:04

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

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

| 下一页