主题：【原创】由一个简单的面试题想起的 -- 东方射日

假设这样一个方案（实际上也没有别的方案）：

先选取一些节点A_0=1<A_1<A_2<……<A_k<A_{k+1}=N，用第一个包裹依次试验这些节点，得到M所在区间A_{s-1}<=M<A_s，然后再用第二个包裹在这个区间里一个个试上去。当M遍历1——>N时，需要的总次数为

现在需要调整As和k的值使得S最小。先对As求偏导得到

2A_k=A_{k-1}+N

2A_s-A_{s+1}-A_{s-1}=1 1<s<k

2A_1=A_2+2

因此A_s=1+as-s^2/2，代入第一个方程（或者直接要求A_{k+1}=N也差不多）得到a=a(N,k)，把A_s和a代入S，得到S=S(N，k)，现在要找一个k使得S最小，对k求偏导并假设N非常大，即得k^2≈2N，S/N≈2k/3≈Sqrt(8N/9)

直接用等差数列（A_s=as+b）得到k^2≈N，S/N≈k≈Sqrt(N)。

• 这个式子不对