给题链接
by cxqghzj @ 2020-05-23 14:26:03
@[cxqghzj](/user/305769) 没有,模拟赛做的题
by Inkyo @ 2020-05-23 14:26:54
。。。
by cxqghzj @ 2020-05-23 14:27:14
直接模拟
by cxqghzj @ 2020-05-23 14:27:39
在百度上就能搜到……是一个01背包,从这 $n$ 个数中选数,使得选的数的和最大且不超过 $\dfrac{sum}{2}$。
by Alan_Zhao @ 2020-05-23 14:28:16
@[Inkyo墨攸](/user/266011)
by Alan_Zhao @ 2020-05-23 14:28:42
@[Alan_Zhao](/user/225625)
啊这
我设计的01背包只能跑 $O(n^2)$
by Inkyo @ 2020-05-23 14:29:58
@[Inkyo墨攸](/user/266011) 是 $O(n\times \text{值域})$ 吧,但你也没说值域啊
by Alan_Zhao @ 2020-05-23 14:31:32
@[Alan_Zhao](/user/225625) 但是 $n$ 是 $10^6$ 级别的,乘个值域会炸
by Inkyo @ 2020-05-23 14:32:47
@[Inkyo墨攸](/user/266011) 那我就没辙了。。。
说句闲话:实名羡慕你们这些有校内模拟赛的,我在弱市弱校,OIer都没几个。。。
by Alan_Zhao @ 2020-05-23 14:37:04