Take you to appreciate the pinduoduo 2020 school entrance examination paper, can you handle this difficulty?

2020-12-08 14:14:50

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]
#define R ch[r]
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