两个算法问题
1.Google面试题，求kth largest elementyou 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最小时的排列.
laile.....................
学习学习!!! .............................................. 楼主，你的高尚情.太让人感动了。在现在这样一个物欲横流的金钱社会里，竟然还能见到楼主这样的性情中人，无疑是我这辈子最大的幸运。让我深深感受到了人性的伟大。楼主的帖子，就好比黑暗中刺裂夜空的闪电，又好比撕开乌云的阳光，一瞬间就让我如饮甘露，让我明白了永恒的真理在这个世界上是真实存在着的。只有楼主这样具备广阔胸怀和完整知识体系的人，才能作为这真理的惟一引言者。 很好！很强大！ 学习学习!!! 很好！很强大！ :D 很好！很强大！ 学习中哦~~~~~~~~~~