当前位置:网站首页>Take you to appreciate the pinduoduo 2020 school entrance examination paper, can you handle this difficulty?

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

2020-12-08 14:14:50 TechFlow2019

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

Link to the original text , Ask for attention

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

版权声明
本文为[TechFlow2019]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012081414192220.html