今天被同学丢了一道题:
两个长度为$n$的数组的内积定义为$\sum_{i=1}^n a_ib_i$。
假如我们改变两个数组中元素的顺序,不难发现两数组同是递增时内积最大,一个递增一个递减时内积最小。
如果算入相同的内积取值,一共有$n!$个数,那么这$n!$个数中第$k$大的是多少呢?
$k$的范围可以是$1e5$或者$1e9$等等,不设上限,$n$同样不设上限。
本人太弱了,目前没有找到比$O(n!)$更优的算法。
自从来到UOJ这个宝地,我的视野变得开阔了,也见识了几位数学大佬,其中肯定不乏富有人类智慧的人士。我相信大佬们一定能给我满意的答案!
求大佬教。