Hello everyone , I wanted to write an article about algorithm and data structure . But take a look at the plan , It's found that basically most of the basic content has been covered . Then there are some competition related algorithms , It's school recruitment season recently , So write a little ** The solution to the pen question **, Maybe it's useful for your recruitment .

This time, I chose one of the test questions of pinduoduo , When I wrote the article, I also saw Ma Zhixing's . That is, the famous one founded by the founder of that building pony.ai, But I click in and have a look , Most of them were **acm The style of the contest question **, The difficulty is a little high for ordinary students . So I didn't adopt , I've changed to pinduoduo .

## The question

Given an integer N, representative N Boxes . The first i There are... In the boxes i A ball .

We can choose one N Natural numbers within X, Duoduo chicken will put more balls in all boxes than X Fewer boxes X A ball . Now? ** Want to clear the balls of all boxes with minimum steps **, How many operations are required at least ？

### Examples

Enter an integer in the first line t, Represents the number of test groups .

Enter an integer for each row N（ ）

It is required to output an integer as the result for each group of data .

## analysis

Let's analyze it a little bit , There are two difficulties in this problem . The first one is this **N It's too big a range **, It's very limited to our complexity . The second point is that the number of balls in the box is dynamic , With such a demanding complexity , It's hard to keep track of all the boxes .

But if you have enough experience , Will find N It's not a limitation, it's a hint .N To reach the scope of 1e9, At this magnitude, we even
All of the calculations will time out , in other words ** All algorithms that need to traverse the box can be abandoned **, It seems harsh , It will save us a lot of time . If N Give me a range of 1e6, That's really disgusting . It is estimated that many students will be cheated , How to think through the calculation of bitter .

Since the scope is 1e9, Well, no one says , The problem must have been worked out in some clever way . But what ingenious method is it , We can't think of it , It's not hard to know , Try to do it and you'll find the way .

Let's assume that we chose... For the first time k, That is, the serial number is greater than or equal to k The number of balls in the box has been reduced k. So what happens after the reduction ？ Let's list it out ： .

Some students may think about the second number when they see this , If you think so , Maybe you don't have enough questions , Not sensitive enough . In fact, you can see that , When we choose k after ,** The array is split into two parts **, On the left is 0 To k-1, On the right is 1 To N-k, middle 0 It's a split line .

What's the use of this discovery ？ It's actually very useful , Let's make a hypothesis first , hypothesis k-1 > N-k, That is, there are more elements on the left than on the right . So no matter what we do next , In fact, as long as our operation can eliminate the left part , The one on the right will naturally disappear . Empathy , If k-1 < N-k, It's the same . So we chose k after , The array is split into two parts ,** The answer has to do with only one part of it **, And it's about the most elemental part of it .

So according to this , We can write expressions directly to express N The answer is ：

This formula looks very complicated. I don't know how to solve it , But it's also very simple , We have one more condition that hasn't been used . Namely **f It must be an increasing function **, This doesn't need to be strictly proved , We can feel it intuitively . since f It's an increasing function , Then the size relationship of many elements in the above formula is obvious .

So the recursion comes out , What we're going to do next is to write out the general terms of this recurrence .

Let's add up all the formulas above ,** On the right f The items will be completely eliminated **, The resulting ：
. This expression has , So the code is natural .

`#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("%d\n", int(log(x)/log(2)) + 1);

}

return 0;

}

## feeling

In fact, the problem is not so difficult , But in the process of the written examination, I met , It is estimated that many students may not be able to do it . It's not because of how difficult the algorithm is , It's that it's going awry in the beginning , Think about how to choose k, For example, to think of recursive solution and so on . such ** The sensitivity and thinking of problems need practice **, You can't get it by reading a few articles or listening to Daniel's lecture .

It's not very difficult for a company to write a test , It's always this kind of thinking problem that needs careful thinking , It's easy to find the routine by doing more and practicing more . If you are interested in these questions, you can take a look at codeforces project , There are a lot of interesting questions in it .

Today's article is here , I wish you every day something to gain . If you still like today's content , One, please ** Three companies support ** Well ~（** give the thumbs-up 、 Focus on 、 forward **）

{{uploading-image-72342.png(uploading...)}}