单规格炸弹(C/Py/Java/Js/Go)题解华为笔试真题 7月1号 非AI方向第二题 200分题型题目内容云小核接到一个爆破任务为了重建老旧一条街需要将这条街上的老建筑全部爆破。云小核拿到一张图显示了这条街上每个建筑的位置还拿到很多炸弹这些炸弹只能部署在建筑里且具有一定的影响范围距离炸弹部署点小于等于炸弹影响范围的建筑会被一起爆破。由于预算有限请你帮云小核计算至少需要多少炸弹才能将所有建筑爆破。输入描述第111行两个整型数值NNNMMM1≤N≤10000001 \le N \le 10000001≤N≤1000000表示建筑数量0≤M≤10000000000 \le M \le 10000000000≤M≤1000000000表示炸弹的影响范围000表示只能爆破炸弹所在位置包括位置相同的建筑。第222行NNN个整型数值n0,n1,...nN−1n0,n1,...nN-1n0,n1,...nN−10ni≤10000000000 ni \le 10000000000ni≤1000000000表示建筑的位置。输出描述一个整型数值表示最少需要的炸弹数量。样例1输入6 10 0 40 5 25 10 50输出3说明至少需要333颗炸弹可部署在101010、252525、505050位置上。样例2输入3 10 10 20 50输出2题解思路思路:贪心需要尽可能少放置炸弹需要让每个炸弹覆盖更多位置。所以尽量让炸弹放置在未覆盖区域中间位置。按照1的逻辑对输入位置进行升序排序。然后模拟统计需要炸弹次数即可。算法时间复杂度为O(logn)C#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intn,m;cinnm;vectorintpos(n);for(inti0;in;i){cinpos[i];}sort(pos.begin(),pos.end());intans0;inti0;// 贪心放置在中间while(in){ans;intleftpos[i];intmidpos[i];i;while(inpos[i]-leftm){midpos[i];i;}while(inpos[i]-midm){i;}}coutans;}javaimportjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[]posnewint[n];for(inti0;in;i){pos[i]sc.nextInt();}Arrays.sort(pos);intans0;inti0;// 贪心放置在中间while(in){ans;intleftpos[i];intmidpos[i];i;while(inpos[i]-leftm){midpos[i];i;}while(inpos[i]-midm){i;}}System.out.print(ans);}}pythondefmain():n,mmap(int,input().split())poslist(map(int,input().split()))pos.sort()ans0i0# 贪心放置在中间whilein:ans1leftpos[i]midpos[i]i1whileinandpos[i]-leftm:midpos[i]i1whileinandpos[i]-midm:i1print(ans,end)if__name____main__:main()javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,(line){input.push(line);});rl.on(close,(){const[n,m]input[0].split( ).map(Number);constposinput[1].split( ).map(Number);pos.sort((a,b)a-b);letans0;leti0;// 贪心放置在中间while(in){ans;constleftpos[i];letmidpos[i];i;while(inpos[i]-leftm){midpos[i];i;}while(inpos[i]-midm){i;}}process.stdout.write(ans.toString());});Gopackagemainimport(bufiofmtossort)funcmain(){in:bufio.NewReader(os.Stdin)varn,mintfmt.Fscan(in,n,m)pos:make([]int,n)fori:0;in;i{fmt.Fscan(in,pos[i])}sort.Ints(pos)ans:0i:0// 贪心放置在中间forin{ansleft:pos[i]mid:pos[i]iforinpos[i]-leftm{midpos[i]i}forinpos[i]-midm{i}}fmt.Print(ans)}
