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 .
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 ？
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 .
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] #define R ch[r] using namespace std; const int N=1000050; const long long Mod=1000000007;
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 ）