走廊通行与按钮策略(C/Py/Java/Js/Go)题解字节跳动笔试真题 4月19号 第一题题目内容你站在一条长度为nnn的走廊起点沿途有编号111到nnn的门每扇门要么开放用000表示要么关闭用111表示。你需要按顺序通过所有门到达出口。你手中有一个特殊按钮至多可以使用KKK次。每次按下按钮会消耗一次使用机会。该次按下的效果是从你当前正要通过的门开始在接下来的xxx秒内即包含当前门在内的连续xxx扇门所有门都将被视为开放状态。给定门的状态序列a1,a2,…,an (ai∈{0,1})a_1,a_2,\dots,a_n\ (a_i \in \{0,1\})a1​,a2​,…,an​(ai​∈{0,1})和按钮最大发动次数KKK请你求出能够通过所有门的最小持续时间xxx。输入描述第一行输入一个整数T (1≤T≤103)T\ (1 \le T \le 10^3)T(1≤T≤103)表示测试用例组数以下共TTT组数据每组格式如下第一行输入两个整数n (1≤n≤2×105)n\ (1 \le n \le 2 \times 10^5)n(1≤n≤2×105)和K (1≤K≤n)K\ (1 \le K \le n)K(1≤K≤n)第二行输入nnn个整数a1,a2,…,an (ai∈{0,1})a_1,a_2,\dots,a_n\ (a_i \in \{0,1\})a1​,a2​,…,an​(ai​∈{0,1})表示第iii扇门的状态。保证所有测试数据中∑n≤2×105\sum n \le 2 \times 10^5∑n≤2×105。输出描述对于每组测试数据输出一个整数表示最小的按钮持续时间xxx。样例1输入3 4 1 0 1 1 0 8 2 1 1 0 1 1 1 0 1 5 3 0 0 0 0 0输出2 4 0说明第一组[0,1,1,0][0,1,1,0][0,1,1,0]中只有一个关闭段长度222K1K1K1需x≥2x \ge 2x≥2才能覆盖故最小x2x2x2第二组在第一扇门前按下按钮通过前444扇门再立即按下按钮通过后444扇门最小x4x4x4第三组所有门均开放无需使用按钮最小x0x0x0。题解和思路思路实现思路二分对于每组输入优先检查是否全为0全为0的情况说明不需要使用按钮直接输出0即可。对于存在非0情况使用二分进行求解定义上下边界left 1, right n, 每次枚举中间值mid (left right) / 2检验在等待时长为mid最多使用按钮次数为k是否能全部通过。边界变动规律为check返回true更新right mid为false更新left mid 1不断循环直到left right结束check的逻辑为从前往后遍历a数组遇到a[i] 1增加使用按钮次数并将i..imid-1设置为0。判断最终使用按钮次数是否小于等于k。总体时间复杂度为O(nlogn)C#includebits/stdc.husingnamespacestd;// 检验等待x情况是否能全部通过boolcheck(intk,intx,vectorinta){intcount0;intna.size();intindex0;while(indexn){if(a[index]0){index;continue;}count;if(countk){returnfalse;}indexx;}returntrue;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,k;cinnk;vectorinta(n);boolallZeroflagtrue;for(inti0;in;i){cina[i];if(a[i]!0){allZeroflagfalse;}}// 检验全为0的情况if(allZeroflag){cout0endl;continue;}intleft1,rightn;while(leftright){intmid(leftright)1;if(check(k,mid,a)){rightmid;}else{leftmid1;}}coutleftendl;}}Javaimportjava.io.*;importjava.util.*;publicclassMain{// 检验等待x情况是否能全部通过staticbooleancheck(intk,intx,int[]a){intcount0;intna.length;intindex0;while(indexn){if(a[index]0){index;continue;}count;if(countk){returnfalse;}indexx;}returntrue;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intTInteger.parseInt(br.readLine());while(T--0){String[]firstbr.readLine().split( );intnInteger.parseInt(first[0]);intkInteger.parseInt(first[1]);String[]arrbr.readLine().split( );int[]anewint[n];booleanallZeroFlagtrue;for(inti0;in;i){a[i]Integer.parseInt(arr[i]);if(a[i]!0){allZeroFlagfalse;}}// 检验全为0的情况if(allZeroFlag){System.out.println(0);continue;}intleft1;intrightn;while(leftright){intmid(leftright)1;if(check(k,mid,a)){rightmid;}else{leftmid1;}}System.out.println(left);}}}pythonimportsys# 检验等待x情况是否能全部通过defcheck(k,x,a):count0nlen(a)index0whileindexn:ifa[index]0:index1continuecount1ifcountk:returnFalseindexxreturnTruedatasys.stdin.read().strip().split()ptr0Tint(data[ptr])ptr1ans[]for_inrange(T):nint(data[ptr])ptr1kint(data[ptr])ptr1a[]all_zero_flagTruefor_inrange(n):vint(data[ptr])ptr1a.append(v)ifv!0:all_zero_flagFalse# 检验全为0的情况ifall_zero_flag:ans.append(0)continueleft1rightnwhileleftright:mid(leftright)//2ifcheck(k,mid,a):rightmidelse:leftmid1ans.append(str(left))print(\n.join(ans))Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(line);});rl.on(close,(){constdatalines.join( ).trim().split(/\s/);letidx0;// 检验等待x情况是否能全部通过functioncheck(k,x,a){letcount0;constna.length;letindex0;while(indexn){if(a[index]0){index;continue;}count;if(countk){returnfalse;}indexx;}returntrue;}constTNumber(data[idx]);constans[];for(lett0;tT;t){constnNumber(data[idx]);constkNumber(data[idx]);consta[];letallZeroFlagtrue;for(leti0;in;i){constvNumber(data[idx]);a.push(v);if(v!0){allZeroFlagfalse;}}// 检验全为0的情况if(allZeroFlag){ans.push(0);continue;}letleft1;letrightn;while(leftright){constmid(leftright)1;if(check(k,mid,a)){rightmid;}else{leftmid1;}}ans.push(String(left));}console.log(ans.join(\n));});Gopackagemainimport(bufiofmtos)// 检验等待x情况是否能全部通过funccheck(kint,xint,a[]int)bool{count:0n:len(a)index:0forindexn{ifa[index]0{indexcontinue}countifcountk{returnfalse}indexx}returntrue}funcmain(){in:bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,T)for;T0;T--{varn,kintfmt.Fscan(in,n,k)a:make([]int,n)allZeroFlag:truefori:0;in;i{fmt.Fscan(in,a[i])ifa[i]!0{allZeroFlagfalse}}// 检验全为0的情况ifallZeroFlag{fmt.Println(0)continue}left:1right:nforleftright{mid:(leftright)1ifcheck(k,mid,a){rightmid}else{leftmid1}}fmt.Println(left)}}