护栏补强拼多多技术岗 8月23号笔试 第二题拼多多真题目录点击查看: 拼多多 春招秋招 笔试真题题库目录笔试题库 算法考点详解题目内容养护队要给一条分成L LL段的护栏做补强。第i ii段当前高度为h i h_ihi​。手册规定最多可以施工T TT次每一次必须选一段连续护栏[ p , q ] [p,q][p,q]且长度不超过W WW也就是1 ≤ p ≤ q ≤ L , q − p 1 ≤ W . 1\le p\le q\le L,\qquad q-p1\le W.1≤p≤q≤L,q−p1≤W.选中后该区间内每一段高度都加1。队里希望补强后「最矮的那段」尽量高。请计算在不超过T TT次施工时整条护栏高度最小值能够达到的最大值。约束写在输入里段数、次数、窗口与高度都不超过1000000000。第二行会给出L LL个高度。输入描述第一行三个整数L LL、T TT、W WW分别表示护栏段数、最多施工次数、单次最多覆盖的连续段数。第二行L LL个整数h 1 , h 2 , … , h L h_1,h_2,\ldots,h_Lh1​,h2​,…,hL​表示各段初始高度。其中1 ≤ L , W ≤ 1000000000 1\le L,W\le 10000000001≤L,W≤10000000000 ≤ T , h i ≤ 1000000000 0\le T,h_i\le 10000000000≤T,hi​≤1000000000。输出描述输出一个整数表示补强后高度最小值的最大可能值。样例1输入4 2 2 3 1 1 3输出3说明两次施工都盖在中间两段[ 2 , 3 ] [2,3][2,3]高度变成3 , 3 , 3 , 3 3,3,3,33,3,3,3最小值为3。再抬高做不到。样例2输入1 10 1 5输出15说明只有一段十次施工都加在它上面高度为5 10 15 5101551015。样例3输入3 0 2 4 2 8输出2说明不能施工最小值仍是2。数据范围1 ≤ L , W ≤ 1000000000 1\le L,W\le 10000000001≤L,W≤10000000000 ≤ T , h i ≤ 1000000000 0\le T,h_i\le 10000000000≤T,hi​≤1000000000第二行包含L LL个整数所有输入均为整数题解思路解题算法:二分 贪心二分上下界下界为min(h), 上界为max(h) T每次枚举中间值mid (l r 1)/ 2使用差分 贪心判断是否能在T次修正过程中保证所有高度大于等于target。满足更新l mid不满足更新r mid - 1算法总体时间复杂度为O(L log(max(h)T))C#includebits/stdc.husingnamespacestd;// 差分 贪心判断boolcheck(vectorlonglongh,longlongtarget,longlongl,longlongt,longlongw){longlongneed0;vectorlonglongprefix(l2,0);for(inti0;il;i){prefix[i1]prefix[i];if(h[i]prefix[i1]target){continue;}else{needtarget-h[i]-prefix[i1];prefix[i1]need;prefix[min(l1,i1w)]-need;}if(needt){returnfalse;}}returntrue;}intmain(){longlongl,t,w;cinltw;vectorlonglongh(l);longlongleftLLONG_MAX;longlongright0;for(inti0;il;i){cinh[i];leftmin(h[i],left);rightmax(h[i],right);}// 二分确定最大可能值rightt;while(leftright){// 向上取整longlongmid(leftright1)1;if(check(h,mid,l,t,w)){leftmid;}else{rightmid-1;}}coutleft;return0;}javaimportjava.io.*;importjava.util.*;// 差分 贪心判断publicclassMain{staticbooleancheck(long[]h,longtarget,intl,longt,longw){longneed0;long[]prefixnewlong[l2];for(inti0;il;i){prefix[i1]prefix[i];if(h[i]prefix[i1]target){continue;}else{needtarget-h[i]-prefix[i1];prefix[i1]need;prefix[(int)Math.min(l1L,i1Lw)]-need;}if(needt){returnfalse;}}returntrue;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringTokenizerstnewStringTokenizer(br.readLine());intlInteger.parseInt(st.nextToken());longtLong.parseLong(st.nextToken());longwLong.parseLong(st.nextToken());long[]hnewlong[l];longleftLong.MAX_VALUE;longright0;stnewStringTokenizer(br.readLine());for(inti0;il;i){h[i]Long.parseLong(st.nextToken());leftMath.min(h[i],left);rightMath.max(h[i],right);}// 二分确定最大可能值rightt;while(leftright){// 向上取整longmid(leftright1)1;if(check(h,mid,l,t,w)){leftmid;}else{rightmid-1;}}System.out.println(left);}}pythonimportsys# 差分 贪心判断defcheck(h,target,l,t,w):need0prefix[0]*(l2)foriinrange(l):prefix[i1]prefix[i]ifh[i]prefix[i1]target:continueelse:needtarget-h[i]-prefix[i1]prefix[i1]need prefix[min(l1,i1w)]-needifneedt:returnFalsereturnTruedatalist(map(int,sys.stdin.buffer.read().split()))ldata[0]tdata[1]wdata[2]hdata[3:3l]leftmin(h)rightmax(h)# 二分确定最大可能值righttwhileleftright:# 向上取整mid(leftright1)1ifcheck(h,mid,l,t,w):leftmidelse:rightmid-1print(left)javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(...line.trim().split(/\s/));});rl.on(close,(){letidx0;constlNumber(lines[idx]);consttNumber(lines[idx]);constwNumber(lines[idx]);consthnewArray(l);letleftNumber.MAX_SAFE_INTEGER;letright0;for(leti0;il;i){h[i]Number(lines[idx]);leftMath.min(h[i],left);rightMath.max(h[i],right);}// 差分 贪心判断functioncheck(h,target,l,t,w){letneed0;constprefixnewArray(l2).fill(0);for(leti0;il;i){prefix[i1]prefix[i];if(h[i]prefix[i1]target){continue;}else{needtarget-h[i]-prefix[i1];prefix[i1]need;prefix[Math.min(l1,i1w)]-need;}if(needt){returnfalse;}}returntrue;}// 二分确定最大可能值rightt;while(leftright){// 向上取整constmidMath.floor((leftright1)/2);if(check(h,mid,l,t,w)){leftmid;}else{rightmid-1;}}console.log(left);});Gopackagemainimport(bufiofmtos)// 差分 贪心判断funccheck(h[]int64,target,l,t,wint64)bool{varneedint64prefix:make([]int64,l2)fori:int64(0);il;i{prefix[i1]prefix[i]ifh[i]prefix[i1]target{continue}else{needtarget-h[i]-prefix[i1]prefix[i1]need pos:i1wifposl1{posl1}prefix[pos]-need}ifneedt{returnfalse}}returntrue}funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varl,t,wint64fmt.Fscan(in,l,t,w)h:make([]int64,l)varleftint64163-1varrightint64fori:int64(0);il;i{fmt.Fscan(in,h[i])ifh[i]left{lefth[i]}ifh[i]right{righth[i]}}// 二分确定最大可能值righttforleftright{// 向上取整mid:(leftright1)1ifcheck(h,mid,l,t,w){leftmid}else{rightmid-1}}fmt.Fprintln(out,left)}