绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
原创 | 带你领略拼多多2020校招笔试题,这样的难度你可以搞定吗?
2020-10-28 16:24:27

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

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

题意

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

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

样例

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

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

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

分析

我们仔细分析一下,会发现这题的难点有两个。个是这个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,bfor (int i=a;i<b;i++)
#define Rep(i,a,bfor (int i=a;i>=b;i--)
#define foreach(e,xfor (__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,xmemset(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, , t) {
        scanf("%d", &x);
        printf("%d\n", int(log(x)/log(2)) + 1);
    }
    return ;
}

感想

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

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

今天的文章就到这里,衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话,请来一个三连支持吧~(点赞、在看、转发

- END -
分享好友

分享这个小栈给你的朋友们,一起进步吧。

TechFlow
创建时间:2020-03-19 11:13:43
机器学习、算法与数据结构、大数据相关和Python。 从纯基础开始的算法领域入门以及进阶内容。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • chengycz
    栈主

小栈成员

查看更多
  • 兔子爱喝红茶
  • 小雨滴
  • ittttliu
  • 栈栈
戳我,来吐槽~