带你领略拼多多 2020 校招笔试题，这样的难度你可以搞定吗？

我就是我 2022-12-19 01:24 66阅读 0赞

大家好，本来今天想写一篇算法和数据结构的。但是看了一眼计划，发现基本上大部分基础的内容都已经讲过了。接下去就是一些竞赛相关的算法了，刚好最近是校招季，所以写一点**笔试题的题解**，也许对大家的招聘有点用。

这一次选了拼多多的校招笔试题其中的一题，在写文章的时候还看到了小马智行的。也就是那个楼教主创办的著名的pony.ai，但是我点进去看了一眼，发现大部分都是**acm竞赛题的风格**，难度对于普通学生而言有些高了。所以没有采纳，改选了拼多多的试题。

## 题意 ##

给定一个整数N，代表N个盒子。第i个盒子当中有i个球。

我们可以选定一个N以内的自然数X，多多鸡会把所有盒中小球数量大于X的盒子减少X个球。现在**想要用最少的步骤将所有盒子的球清空**，请问最少需要多少次操作？

### 样例 ###

第一行输入一个整数t，表示测试组数。

对于每一行都输入一个整数N（）

要求对于每组数据输出一个整数作为结果。

![format_png][]

## 分析 ##

我们仔细分析一下，会发现这题的难点有两个。第一个是这个**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("%d\n", int(log(x)/log(2)) + 1);
        }
        return 0;
    }

## 感想 ##

这道题从难度上来讲其实不大，但是真正在笔试的过程当中遇到，估计很多同学可能做不出来。倒不是因为算法有多难，而是会一开始的时候就走了歪路，比如去思考怎么样选择k，比如去想递推的解法等等。这种**对问题的敏感和思路是需要练习的**，并不是看几篇文章或者是听听大牛讲课就可以获得的。

一般公司的笔试题不会很难，往往都是这种需要缜密思考的思维题，这种题多做多练很容易就摸到套路了。如果对这些问题感兴趣可以看看codeforces专题，里面有很多有趣的思维题。

--------------------

### **推荐阅读** ###

• [吴师兄实名吐槽 LeetCode 上的一道题目。。。][LeetCode]• [面试字节跳动时，我竟然遇到了原题……][Link 1]• [计算机专业的学生怎样练习编程才能把编程学精通？][Link 2]• [为什么 MySQL 使用 B+ 树][MySQL _ B_]• [一道简简单单的字节跳动算法面试题][Link 3]

--------------------

欢迎关注我的公众号“**五分钟学算法**”，如果喜欢，麻烦点一下“**在看**”~

![format_png 1][]

[format_png]: /images/20221120/aaebaa052efa45d2b63d9d824d2f98f0.png
[LeetCode]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75efcd79fcf9c65ebb5070122b9705e18cb1c46b06c5eb3e299520ed4a25e327bc07bb4b&idx=2&mid=2247490158&scene=21&sn=12e587a361f0df072d2dc164c219a61e#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e75aecd79fcb8b5f932c7ba5ed7a9e34a6c99f20bc129cef33774167d668e8745755d02ad&idx=1&mid=2247490095&scene=21&sn=baa0379b1ca62db17327a2cb825a1b24#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0d87aacd7a0ebc3ada34a076d1fa3943ee24097966257132b1042b7a3e4debedc78f38c8cf&idx=1&mid=2247493675&scene=21&sn=6b501ef2032ab911f0a3519eb7397017#wechat_redirect
[MySQL _ B_]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e759ccd79fc8a73c77eacfd7c8b1391b08864e2e13fdf5a6e41e218a499d5a87ee12e4e6a&idx=2&mid=2247490077&scene=21&sn=56c52b385c98c7f0ad33c2621da101eb#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e767dcd79ff6b2733dd8905f188afb19eb400d5e644f5b5127f909ee7c3583786031f9c20&idx=2&mid=2247490044&scene=21&sn=bb3610dfedbb2e0c017c3ff3d5e4684b#wechat_redirect
[format_png 1]: /images/20221120/0b3c3fd1a65e48448e6a835b5aeda637.png