)
小红书机考真题- 最小化峰值干扰整理历年互联网大厂机考、机试真题与面试真题覆盖校招、实习招聘等常见求职场景包含高频算法题、编程题、机考题及面试题并提供完整代码、解题思路、代码详解和在线 OJ 练习方便系统刷题和备战大厂技术面试。点击查看完整题库目录互联网大厂历年机考机试与面试真题题库代码详解在线OJ题目描述要将 m 项探测任务按给定顺序安排到连续 n 个时隙。第 j 个时隙的干扰强度为 aj第 i 项任务占用连续 bi 个时隙。记 li 为第 i 项任务的起始时隙则其占用区间为 [li,libi−1]。安排须满足任务占用互不重叠对任意 ij有 libi−1lj任务之间可空出任意个时隙。任务保持给定顺序l1l2⋯lm。均落在时隙范围内1≤li 且 libi−1≤n。峰值干扰为max i 1 m max j l i l i b i − 1 a j \max_{i1}^{m}\max_{jl_i}^{l_ib_i-1} a_ji1maxmjlimaxlibi−1aj求所有合法安排下峰值干扰的最小值。输入描述第一行一个正整数 T表示测试数据组数。对于每组测试数据第一行两个正整数 n,m表示时隙数和任务数。第二行 n 个正整数 a1,a2,…,an表示每个时隙的干扰强度。第三行 m 个正整数 b1,b2,…,bm表示每项任务占用的时隙数。数据范围1≤T≤200000所有测试数据的 n 之和 ≤2000001≤n1≤m1≤ai≤10^91≤bi≤n∑bi≤n。输出描述对于每组测试数据输出一行一个整数表示峰值干扰的最小值。示例1输入2 7 2 8 1 3 5 2 1 4 2 3 6 3 2 8 1 1 3 1 1 1 2输出4 3说明第一组第一项任务放在 [2,3]覆盖 1,3最大值 3第二项放在 [5,7]覆盖 2,1,4最大值 4。峰值干扰为 max(3,4)4。若要求峰值不超过 3则时隙 1、4、7 不可用剩余连续段长度不足以放下长度为 3 的第二项任务。第二组三项任务分别放在时隙 1、3 与 [4,5]覆盖 211,3峰值干扰为 max(2,1,3)3。若要求峰值不超过 2则时隙 2、5 不可用无法为第三项任务找到长度为 2 的连续段。解题思路本题采用【二分答案 贪心】算法假设峰值干扰上限为x那么干扰强度大于x的时隙不能被任何任务占用其余时隙可以使用。问题转化为判断能否按给定顺序为每项任务找到长度为bi的连续可用区间。可行性检查时从左向右扫描时隙并让每项任务在剩余时隙中尽早结束。扫描过程中记录连续满足aj≤x的时隙数量达到当前任务长度后立刻安排该任务再从其结束位置之后继续安排下一项。最早结束会给后续任务留下最多空间若这种安排仍失败其他安排也不可能成功。随着上限x增大可用时隙只会增加可行性具有单调性。因此在干扰数组的最小值与最大值之间二分找到第一个能够完成全部任务的上限即为最小峰值干扰。Javaimportjava.util.Scanner;publicclassMain{staticbooleancanPlace(long[]a,int[]b,longlimit){intpos0;for(intneed:b){intrun0;while(posa.lengthrunneed){runa[pos]limit?run1:0;pos;}if(runneed)returnfalse;}returntrue;}staticlongsolve(long[]a,int[]b){// 答案位于干扰强度的最小值和最大值之间longlowa[0],higha[0];for(longvalue:a){lowMath.min(low,value);highMath.max(high,value);}// 二分最小可行峰值并用贪心检查任务能否按顺序放置while(lowhigh){longmidlow(high-low)/2;if(canPlace(a,b,mid))highmid;elselowmid1;}returnlow;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);inttsc.nextInt();StringBuilderoutnewStringBuilder();for(inttc0;tct;tc){intnsc.nextInt(),msc.nextInt();long[]anewlong[n];int[]bnewint[m];for(inti0;in;i)a[i]sc.nextLong();for(inti0;im;i)b[i]sc.nextInt();if(tc0)out.append(\n);out.append(solve(a,b));}System.out.println(out);}}Pythondefcan_place(a,b,limit):position0forneedinb:consecutive0whilepositionlen(a)andconsecutiveneed:consecutiveconsecutive1ifa[position]limitelse0position1ifconsecutiveneed:returnFalsereturnTruedefsolve(a,b):# 答案位于干扰强度的最小值和最大值之间low,highmin(a),max(a)# 二分最小可行峰值并用贪心检查任务能否按顺序放置whilelowhigh:middle(lowhigh)//2ifcan_place(a,b,middle):highmiddleelse:lowmiddle1returnlowdefmain():test_countint(input())answers[]for_inrange(test_count):n,mmap(int,input().split())alist(map(int,input().split()))blist(map(int,input().split()))answers.append(str(solve(a,b)))print(\n.join(answers))if__name____main__:main()JavaScriptconstreadlinerequire(readline);functioncanPlace(a,b,limit){letposition0;for(constneedofb){letconsecutive0;while(positiona.lengthconsecutiveneed){consecutivea[position]limit?consecutive1:0;position;}if(consecutiveneed)returnfalse;}returntrue;}functionsolve(a,b){// 答案位于干扰强度的最小值和最大值之间letlowa[0],higha[0];for(constvalueofa){lowMath.min(low,value);highMath.max(high,value);}// 二分最小可行峰值并用贪心检查任务能否按顺序放置while(lowhigh){constmiddleMath.floor((lowhigh)/2);if(canPlace(a,b,middle))highmiddle;elselowmiddle1;}returnlow;}constrlreadline.createInterface({input:process.stdin,crlfDelay:Infinity});constlines[];rl.on(line,linelines.push(line.trim()));rl.on(close,(){letk0;consttNumber(lines[k]);constout[];for(lettc0;tct;tc){const[n,m]lines[k].split(/\s/).map(Number);constalines[k].split(/\s/).map(Number);constblines[k].split(/\s/).map(Number);out.push(String(solve(a,b)));}console.log(out.join(\n));});C#includealgorithm#includeiostream#includevectorusingnamespacestd;boolcanPlace(constvectorlonglonga,constvectorintb,longlonglimit){intposition0;for(intneed:b){intconsecutive0;while(position(int)a.size()consecutiveneed){consecutivea[position]limit?consecutive1:0;position;}if(consecutiveneed)returnfalse;}returntrue;}longlongsolve(constvectorlonglonga,constvectorintb){// 答案位于干扰强度的最小值和最大值之间autoboundsminmax_element(a.begin(),a.end());longlonglow*bounds.first,high*bounds.second;// 二分最小可行峰值并用贪心检查任务能否按顺序放置while(lowhigh){longlongmiddlelow(high-low)/2;if(canPlace(a,b,middle))highmiddle;elselowmiddle1;}returnlow;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cint;for(inttc0;tct;tc){intn,m;cinnm;vectorlonglonga(n);vectorintb(m);for(autox:a)cinx;for(autox:b)cinx;coutsolve(a,b)(tc1t?\n:\n);}}Gopackagemainimport(bufiofmtos)funccanPlace(a[]int64,b[]int,limitint64)bool{position:0for_,need:rangeb{consecutive:0forpositionlen(a)consecutiveneed{ifa[position]limit{consecutive}else{consecutive0}position}ifconsecutiveneed{returnfalse}}returntrue}funcsolve(a[]int64,b[]int)int64{// 答案位于干扰强度的最小值和最大值之间low,high:a[0],a[0]for_,value:rangea{ifvaluelow{lowvalue};ifvaluehigh{highvalue}}// 二分最小可行峰值并用贪心检查任务能否按顺序放置forlowhigh{middle:low(high-low)/2ifcanPlace(a,b,middle){highmiddle}else{lowmiddle1}}returnlow}funcmain(){in:bufio.NewReader(os.Stdin);out:bufio.NewWriter(os.Stdout);deferout.Flush()vartint;fmt.Fscan(in,t)fortc:0;tct;tc{varn,mint;fmt.Fscan(in,n,m);a:make([]int64,n);b:make([]int,m)fori:rangea{fmt.Fscan(in,a[i])};fori:rangeb{fmt.Fscan(in,b[i])}fmt.Fprintln(out,solve(a,b))}}C语言#includestdint.h#includestdio.h#includestdlib.hintcanPlace(constlonglong*a,intn,constint*b,intm,longlonglimit){intposition0;for(inttask0;taskm;task){intconsecutive0;while(positionnconsecutiveb[task]){consecutivea[position]limit?consecutive1:0;position;}if(consecutiveb[task])return0;}return1;}longlongsolve(constlonglong*a,intn,constint*b,intm){// 答案位于干扰强度的最小值和最大值之间longlonglowa[0],higha[0];for(inti1;in;i){if(a[i]low)lowa[i];if(a[i]high)higha[i];}// 二分最小可行峰值并用贪心检查任务能否按顺序放置while(lowhigh){longlongmiddlelow(high-low)/2;if(canPlace(a,n,b,m,middle))highmiddle;elselowmiddle1;}returnlow;}intmain(void){intt;if(scanf(%d,t)!1)return0;for(inttc0;tct;tc){intn,m;scanf(%d%d,n,m);longlong*amalloc((size_t)n*sizeof(longlong));int*bmalloc((size_t)m*sizeof(int));for(inti0;in;i)scanf(%lld,a[i]);for(inti0;im;i)scanf(%d,b[i]);printf(%lld\n,solve(a,n,b,m));free(a);free(b);}return0;}完整用例用例12 7 2 8 1 3 5 2 1 4 2 3 6 3 2 8 1 1 3 1 1 1 2用例23 1 1 7 1 5 1 5 4 3 2 1 5 5 5 9 1 8 2 7 1 1 1 1 1用例32 8 2 9 1 1 9 2 2 2 9 2 3 10 3 1 100 1 1 100 2 2 2 100 1 1 2 1用例42 6 2 1 1 9 2 2 2 3 2 6 2 1 1 9 2 2 2 2 3用例53 12 3 5 5 1 1 1 5 2 2 5 3 3 3 3 2 3 7 2 4 1 4 1 4 1 4 2 2 6 3 6 6 6 6 6 6 2 1 3用例63 7 2 1000000000 1 500000000 1 1000000000 2 2 2 2 6 2 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 5 3 1 999999999 1 999999998 1 1 1 1用例73 10 2 10 9 8 7 6 5 4 3 2 1 2 2 10 3 1 2 3 4 5 6 7 8 9 10 3 1 2 9 4 5 1 5 1 5 1 5 1 5 1 1 1 1用例82 8 2 3 1 1 5 2 2 4 1 2 2 9 3 1 4 1 4 1 4 1 4 1 1 1 1用例92 6 2 1 1 8 2 2 2 2 3 6 2 1 1 8 2 2 2 3 2用例103 4 1 7 2 3 4 2 5 2 5 1 1 5 1 2 1 10 3 2 9 2 2 9 3 3 3 9 1 1 2 1
