$$ \text{首先可以证明，把原局面从到大小一个一个关所经历的步数一定最少} \\ \left( \text{每次必定选择编号最大的没有关闭的灯} \right) \text{所以先求出来这个步数。} \\ \text{如果这个步数不超过}k\text{，那么这个步数就是答案。} \\ \text{否则设}f\left( i \right) \text{表示还剩}i\text{步的时候，随机选择一个开关是转移到还剩}i-\text{1步的期望步数。} \\ f\left( i \right) =\frac{i}{n}\left( \text{选中了一个正确的开关} \right) +\left( 1-\frac{i}{n} \right) \left( f\left( i \right) +f\left( i+1 \right) +1 \right) \left( \text{选中了一个错误的开关，那么步数}+1 \right) \\ \text{显然}f\left( n \right) =\text{1，此时随便选一个开关都会让步数少}1. \\ \text{整理得}f\left( i \right) =1+\frac{n-i}{i}\left( f\left( i+1 \right) +1 \right) \\ \text{计算出}f\left( k+1 \right) \text{到}f\left( n \right) \text{的答案累加起来，加上}k\text{即可。} \\ $