帶你領(lǐng)略拼多多2020校招筆試題，這樣的難度你可以搞定嗎？
大家好，本來(lái)今天想寫(xiě)一篇算法和數(shù)據(jù)結(jié)構(gòu)的。但是看了一眼計(jì)劃，發(fā)現(xiàn)基本上大部分基礎(chǔ)的內(nèi)容都已經(jīng)講過(guò)了。接下去就是一些競(jìng)賽相關(guān)的算法了，剛好最近是校招季，所以寫(xiě)一點(diǎn)筆試題的題解，也許對(duì)大家的招聘有點(diǎn)用。
這一次選了拼多多的校招筆試題其中的一題，在寫(xiě)文章的時(shí)候還看到了小馬智行的。也就是那個(gè)樓教主創(chuàng)辦的著名的pony.ai，但是我點(diǎn)進(jìn)去看了一眼，發(fā)現(xiàn)大部分都是acm競(jìng)賽題的風(fēng)格，難度對(duì)于普通學(xué)生而言有些高了。所以沒(méi)有采納，改選了拼多多的試題。
題意
給定一個(gè)整數(shù)N，代表N個(gè)盒子。第i個(gè)盒子當(dāng)中有i個(gè)球。
我們可以選定一個(gè)N以內(nèi)的自然數(shù)X，多多雞會(huì)把所有盒中小球數(shù)量大于X的盒子減少X個(gè)球?，F(xiàn)在想要用最少的步驟將所有盒子的球清空，請(qǐng)問(wèn)最少需要多少次操作？
樣例
第一行輸入一個(gè)整數(shù)t，表示測(cè)試組數(shù)。
對(duì)于每一行都輸入一個(gè)整數(shù)N（）
要求對(duì)于每組數(shù)據(jù)輸出一個(gè)整數(shù)作為結(jié)果。
分析
我們仔細(xì)分析一下，會(huì)發(fā)現(xiàn)這題的難點(diǎn)有兩個(gè)。第一個(gè)是這個(gè)N的范圍太大了，對(duì)我們的復(fù)雜度限制得很高。第二點(diǎn)是盒子當(dāng)中球的數(shù)量是動(dòng)態(tài)的，在如此苛刻的復(fù)雜度要求下，我們很難掌握所有盒子的動(dòng)態(tài)。
但如果你有足夠多經(jīng)驗(yàn)的話，會(huì)發(fā)現(xiàn)N的范圍其實(shí)并不是限制而是提示。N的范圍達(dá)到1e9，在這個(gè)量級(jí)下我們連的計(jì)算都是會(huì)超時(shí)的，也就是說(shuō)所有需要遍歷盒子的算法都可以放棄了，看似苛刻，其實(shí)會(huì)節(jié)省我們很多時(shí)間。如果N的范圍給個(gè)1e6，那才是真的惡心。估計(jì)很多同學(xué)要被騙了，苦苦思考怎么樣通過(guò)模擬的方法來(lái)計(jì)算。
既然范圍是1e9，那么沒(méi)的說(shuō)，這題一定是通過(guò)一些巧妙的方法來(lái)計(jì)算的。但是究竟是什么巧妙的方法，我們干想是想不出來(lái)的，要想知道也不難，嘗試著去做一下就可以找到門(mén)道了。
我們假設(shè)我們第一次選擇了k，也就是序號(hào)大于等于k的盒子里球的數(shù)量都減少了k。那么減少之后的情況變成什么樣了呢？我們列出來(lái)看看：。
有些同學(xué)看到這個(gè)可能會(huì)想第二個(gè)數(shù)字選什么，如果你這么想了，可能你做的題目還不夠多，不夠敏感。其實(shí)看到這個(gè)已經(jīng)可以發(fā)現(xiàn)，當(dāng)我們選擇了k之后，數(shù)組被拆分成了兩個(gè)部分，左邊是0到k-1，右邊是1到N-k，中間0是分割線。
這一點(diǎn)發(fā)現(xiàn)有什么用呢？其實(shí)很有用，我們首先來(lái)做一個(gè)假設(shè)，假設(shè)k-1 > N-k，也就是左邊部分的元素比右邊更多。那么不管我們接下來(lái)如何操作，其實(shí)只要我們的操作能夠消除掉左邊的部分，右邊的自然也會(huì)跟著消除。同理，如果k-1 < N-k，也是一樣的。所以我們通過(guò)選擇了k之后，數(shù)組拆分成了兩個(gè)部分，答案只和其中的一個(gè)部分有關(guān)，并且是和其中元素最多的部分有關(guān)。
那么根據(jù)這一點(diǎn)，我們可以直接寫(xiě)出表達(dá)式來(lái)表示N時(shí)的答案：
這個(gè)式子看起來(lái)很復(fù)雜不知道如何解，但其實(shí)也很簡(jiǎn)單，我們還有一個(gè)條件沒(méi)有用上。就是f必然是一個(gè)遞增函數(shù)，這個(gè)其實(shí)不需要嚴(yán)格證明，我們直觀上就可以感受出來(lái)。既然f是遞增函數(shù)，那么上面式子當(dāng)中很多元素的大小關(guān)系就都明顯了。
這樣遞推式就出來(lái)了，我們接下來(lái)要做的就是根據(jù)這個(gè)遞推式寫(xiě)出它的通項(xiàng)。
我們把上面的式子全部累加在一起，右邊帶有f的項(xiàng)會(huì)被全部消掉，最終得到：。這個(gè)表達(dá)式有了，那么代碼自然手到擒來(lái)。
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?
#include?"time.h"
#include?
#define?rep(i,a,b)?for?(int?i=a;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;
}
感想
這道題從難度上來(lái)講其實(shí)不大，但是真正在筆試的過(guò)程當(dāng)中遇到，估計(jì)很多同學(xué)可能做不出來(lái)。倒不是因?yàn)樗惴ㄓ卸嚯y，而是會(huì)一開(kāi)始的時(shí)候就走了歪路，比如去思考怎么樣選擇k，比如去想遞推的解法等等。這種對(duì)問(wèn)題的敏感和思路是需要練習(xí)的，并不是看幾篇文章或者是聽(tīng)聽(tīng)大牛講課就可以獲得的。
一般公司的筆試題不會(huì)很難，往往都是這種需要縝密思考的思維題，這種題多做多練很容易就摸到套路了。如果對(duì)這些問(wèn)題感興趣可以看看codeforces專題，里面有很多有趣的思維題。
往期推薦
所有原創(chuàng)文章已整合成 PDF，名稱為《程序員內(nèi)功修煉》，后臺(tái)回復(fù)「PDF」即可獲取。
我的小號(hào)：「我是帥地」，分享技術(shù)之外的故事，感興趣可以關(guān)注