题意
给定一个整数N，代表N个盒子。第i个盒子当中有i个球。
咱们能够选定一个N以内的自然数X，多多鸡会把所有盒中小球数量大于X的盒子缩小X个球。当初想要用起码的步骤将所有盒子的球清空，请问起码须要多少次操作？
样例
第一行输出一个整数t，示意测试组数。
对于每一行都输出一个整数N（）
要求对于每组数据输入一个整数作为后果。
剖析
咱们仔细分析一下，会发现这题的难点有两个。第一个是这个N的范畴太大了，对咱们的复杂度限度得很高。第二点是盒子当中球的数量是动静的，在如此刻薄的复杂度要求下，咱们很难把握所有盒子的动静。
但如果你有足够多教训的话，会发现N的范畴其实并不是限度而是提醒。N的范畴达到1e9，在这个量级下咱们连的计算都是会超时的，也就是说所有须要遍历盒子的算法都能够放弃了，看似刻薄，其实会节俭咱们很多工夫。如果N的范畴给个1e6，那才是真的恶心。预计很多同学要被骗了，苦苦思考怎么样通过模仿的办法来计算。
既然范畴是1e9，那么没的说，这题肯定是通过一些奇妙的办法来计算的。然而到底是什么奇妙的办法，咱们干想是想不进去的，要想晓得也不难，尝试着去做一下就能够找到门道了。
咱们假如咱们第一次抉择了k，也就是序号大于等于k的盒子里球的数量都缩小了k。那么缩小之后的状况变成什么样了呢？咱们列出来看看：。
有些同学看到这个可能会想第二个数字选什么，如果你这么想了，可能你做的题目还不够多，不够敏感。其实看到这个曾经能够发现，当咱们抉择了k之后，数组被拆分成了两个局部，右边是0到k-1，左边是1到N-k，两头0是分割线。
这一点发现有什么用呢？其实很有用，咱们首先来做一个假如，假如k-1 > N-k，也就是右边局部的元素比左边更多。那么不论咱们接下来如何操作，其实只有咱们的操作可能打消掉右边的局部，左边的天然也会跟着打消。同理，如果k-1 < N-k，也是一样的。所以咱们通过抉择了k之后，数组拆分成了两个局部，答案只和其中的一个局部无关，并且是和其中元素最多的局部无关。
那么依据这一点，咱们能够间接写出表达式来示意N时的答案：
这个式子看起来很简单不晓得如何解，但其实也很简略，咱们还有一个条件没有用上。就是f必然是一个递增函数，这个其实不须要严格证实，咱们直观上就能够感触进去。既然f是递增函数，那么下面式子当中很多元素的大小关系就都显著了。
这样递推式就进去了，咱们接下来要做的就是依据这个递推式写出它的通项。
咱们把下面的式子全副累加在一起，左边带有f的项会被全副消掉，最终失去：。这个表达式有了，那么代码天然手到擒来。
#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <cmath>#include <cstdlib>#include <string>#include <map>#include <set>#include <algorithm>#include "time.h"#include <functional>#define rep(i,a,b) for (int i=a;i<b;i++)#define Rep(i,a,b) for (int i=a;i>=b;i--)#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)#define mid ((l+r)>>1)#define lson (k<<1)#define rson (k<<1|1)#define MEM(a,x) memset(a,x,sizeof a)#define L ch[r][0]#define R ch[r][1]using namespace std;const int N=1000050;const long long Mod=1000000007;int t, x;int main() { scanf("%d", &t); rep(z, 0, t) { scanf("%d", &x); printf("%dn", int(log(x)/log(2)) + 1); } return 0;} 感想
这道题从难度上来讲其实不大，然而真正在口试的过程当中遇到，预计很多同学可能做不进去。倒不是因为算法有多难，而是会一开始的时候就走了歪路，比方去思考怎么样抉择k，比方去想递推的解法等等。这种对问题的敏感和思路是须要练习的，并不是看几篇文章或者是听听大牛讲课就能够取得的。
个别公司的口试题不会很难，往往都是这种须要周密思考的思维题，这种题多做多练很容易就摸到套路了。如果对这些问题感兴趣能够看看codeforces专题，外面有很多乏味的思维题。好了，今日分享到这就完结了，喜爱能够点个关注哦。