两个算法问题

ccf19881030

1.Google面试题，求kth largest element


you are given 2 arrays sorted in decreasing order of size m and n  
respectively.

Input: a number k <= n*m and >= 1

Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)

两个数组A,B 求第k个sum(a+b)。

如果直接一个一个算的话，从大到小，需要O(k)复杂度。
有没有O(logk)或者O(1)的方法。


2.排列与统筹学结合的经典问题


问题：
设方程组（如下）有解：
X1+3+X12=X2
X2+4+X13=X3
X2+4+X14=X4
X3+5+X15=X5
X4+7+X16=X5
X5+8+X17=X6
X6+1+X18=48
X7+5+X19=X8
X8+1+X20=X9
X8+1+X21=X10
X10+2+X22=29
X9+9+X23=X11
X11+7+X24=29
(Xi≥0;i =1,2,…24)

集合:
A={X1,X3,X5,X7,X8,X10,X11};
B={X2,X4,X6,X9};

设A中元素组成m组排列,B中元素组成n组排列.
每个集合中的元素取且仅取一次.(如A中可以形成3组排列:X3X8X7,X1,X5X10X11)
每个排列中元素按照排列顺序满足条件:
Xi+Txi≤Xj (j为排在i后元素,Txi为Xi所在上述方程式左侧时,该方程式中的常量,如Tx2=4)

(如:排列X1X3X7,满足条件
X1+3≤X3
X3+5≤X7 )


求满足方程组时,m+n最小时的排列.

peter1977

GOOGle 面试题还是有高度的。。。

540136593

不错不错学习了

LYJA

楼主好人，谢谢！！！！！！！！！！！！！！！！！！！！！！

流雨星月

挺好的，顶一下

模天大楼

喜欢就收下了\(^o^)/~

499379348

这么多回复却是“由题无解”..

1221long

真的挺难的~

乖乖1503155

学过啦yeo

shuxuezaozhuang

谢谢你！！

chenxs008

good ,thks