question about changing return ticket for CA# Reunion - 探亲与陪读
g*y
1 楼
November 02
总结下最近几天看到的一些很有趣的题目
题目1. LIS. 一个任意的数组，找出一个严格单调递增的最长子序列。
例如: {3,0,1,7,2,4,5,9} –> output： {0, 1, 2, 4, 5, 9}
很简洁巧妙的算法，能在O(N log N)时间和O(N)空间做出来！方法就是始终保持一个单
增的序列，然后新来的数如果比当前最大还大就append在后面，否则在单增序列里面做
binary search，替换相应位置的数。
题目2. 玻璃杯/鸡蛋drop问题。有N层楼，假定是在 i 层楼扔鸡蛋，如果没有碎，那么
在所有<=i 楼层扔鸡蛋都保证不会碎，反之如果碎了，那么保证在所有 >=i 楼层扔鸡
蛋都必碎。通过若干次尝试扔鸡蛋，找到某个鸡蛋碎/不碎的”临界”层。允许你扔鸡
蛋的总次数是D，允许你打碎的鸡蛋数是B。
问题的描述是：对一组给定的数（N D B），如果存在一个策略保证能在D B的限制下，
在N层楼中找到“临界”层，那么称此(N D B)是Solvable的。接下来相关联的三个问题
就是:
（a）给定D，B，求满足（N，D，B）Solvable
总结下最近几天看到的一些很有趣的题目
题目1. LIS. 一个任意的数组，找出一个严格单调递增的最长子序列。
例如: {3,0,1,7,2,4,5,9} –> output： {0, 1, 2, 4, 5, 9}
很简洁巧妙的算法，能在O(N log N)时间和O(N)空间做出来！方法就是始终保持一个单
增的序列，然后新来的数如果比当前最大还大就append在后面，否则在单增序列里面做
binary search，替换相应位置的数。
题目2. 玻璃杯/鸡蛋drop问题。有N层楼，假定是在 i 层楼扔鸡蛋，如果没有碎，那么
在所有<=i 楼层扔鸡蛋都保证不会碎，反之如果碎了，那么保证在所有 >=i 楼层扔鸡
蛋都必碎。通过若干次尝试扔鸡蛋，找到某个鸡蛋碎/不碎的”临界”层。允许你扔鸡
蛋的总次数是D，允许你打碎的鸡蛋数是B。
问题的描述是：对一组给定的数（N D B），如果存在一个策略保证能在D B的限制下，
在N层楼中找到“临界”层，那么称此(N D B)是Solvable的。接下来相关联的三个问题
就是:
（a）给定D，B，求满足（N，D，B）Solvable
