UOJ Logo hzoi2017_csm的博客

博客

蒟蒻求教

2019-04-15 16:20:49 By hzoi2017_csm

今天被同学丢了一道题:

两个长度为$n$的数组的内积定义为$\sum_{i=1}^n a_ib_i$。

假如我们改变两个数组中元素的顺序,不难发现两数组同是递增时内积最大,一个递增一个递减时内积最小。

如果算入相同的内积取值,一共有$n!$个数,那么这$n!$个数中第$k$大的是多少呢?

$k$的范围可以是$1e5$或者$1e9$等等,不设上限,$n$同样不设上限。

本人太弱了,目前没有找到比$O(n!)$更优的算法。

自从来到UOJ这个宝地,我的视野变得开阔了,也见识了几位数学大佬,其中肯定不乏富有人类智慧的人士。我相信大佬们一定能给我满意的答案!

求大佬教。

评论

peehs_moorhsum
要是a,b可能很大,显然是不可做的QAQ 你令b都是零一,二分一下,你就解决了背包?
lyx_cjz
根据楼上的观点应该多项式是不行的,但比 $O(n!)$ 优秀的指数算法还是有的。 首先二分答案,考虑计算此时选择方案。 $O\left(\dbinom{n}{n/2}\right)$枚举前 $n/2$ 个a匹配的b位置的集合,分别暴力前一半和后一半的选择方法,然后排序一下二分一下就可以 $O((n/2)!\cdot \mathrm{poly}(n))$ 总的复杂度大概是 $O(n!/(n/2)!\cdot \mathrm{poly}(n))$ 的,比阶乘稍微好一些。
TDL5
有$$O(klog^2n)$$的做法并已经被人出过 https://godcowc.github.io/2016/06/18/20160618-water/

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。