共计 2028 个字符，预计需要花费 6 分钟才能阅读完成。
题意
给定一个整数 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 专题，外面有很多乏味的思维题。好了，今日分享到这就完结了，喜爱能够点个关注哦。
