单规格炸弹(C++/Py/Java/Js/Go)题解

华为笔试真题 7月1号 非AI方向第二题 200分题型

题目内容

云小核接到一个爆破任务，为了重建老旧一条街，需要将这条街上的老建筑全部爆破。云小核拿到一张图，显示了这条街上每个建筑的位置，还拿到很多炸弹，这些炸弹只能部署在建筑里，且具有一定的影响范围，距离炸弹部署点小于等于炸弹影响范围的建筑，会被一起爆破。由于预算有限，请你帮云小核计算至少需要多少炸弹，才能将所有建筑爆破。

输入描述

第111行：两个整型数值：NNN，MMM，1≤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−1，0<ni≤10000000000 < ni \le 10000000000<ni≤1000000000，表示建筑的位置。

输出描述

一个整型数值，表示最少需要的炸弹数量。

样例1

输入

6 10 0 40 5 25 10 50

输出

3

说明
至少需要333颗炸弹，可部署在101010、252525、505050位置上。

样例2

输入

3 10 10 20 50

输出

2

题解

思路

思路:贪心

1. 需要尽可能少放置炸弹，需要让每个炸弹覆盖更多位置。所以尽量让炸弹放置在未覆盖区域中间位置。
2. 按照1的逻辑对输入位置进行升序排序。
3. 然后模拟统计需要炸弹次数即可。
4. 算法时间复杂度为O(logn)

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intn,m;cin>>n>>m;vector<int>pos(n);for(inti=0;i<n;i++){cin>>pos[i];}sort(pos.begin(),pos.end());intans=0;inti=0;// 贪心，放置在中间while(i<n){ans++;intleft=pos[i];intmid=pos[i];i++;while(i<n&&pos[i]-left<=m){mid=pos[i];i++;}while(i<n&&pos[i]-mid<=m){i++;}}cout<<ans;}

java

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();intm=sc.nextInt();int[]pos=newint[n];for(inti=0;i<n;i++){pos[i]=sc.nextInt();}Arrays.sort(pos);intans=0;inti=0;// 贪心，放置在中间while(i<n){ans++;intleft=pos[i];intmid=pos[i];i++;while(i<n&&pos[i]-left<=m){mid=pos[i];i++;}while(i<n&&pos[i]-mid<=m){i++;}}System.out.print(ans);}}

python

defmain():n,m=map(int,input().split())pos=list(map(int,input().split()))pos.sort()ans=0i=0# 贪心，放置在中间whilei<n:ans+=1left=pos[i]mid=pos[i]i+=1whilei<nandpos[i]-left<=m:mid=pos[i]i+=1whilei<nandpos[i]-mid<=m:i+=1print(ans,end="")if__name__=="__main__":main()

javascript

constreadline=require("readline");constrl=readline.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);constpos=input[1].split(" ").map(Number);pos.sort((a,b)=>a-b);letans=0;leti=0;// 贪心，放置在中间while(i<n){ans++;constleft=pos[i];letmid=pos[i];i++;while(i<n&&pos[i]-left<=m){mid=pos[i];i++;}while(i<n&&pos[i]-mid<=m){i++;}}process.stdout.write(ans.toString());});

Go

packagemainimport("bufio""fmt""os""sort")funcmain(){in:=bufio.NewReader(os.Stdin)varn,mintfmt.Fscan(in,&n,&m)pos:=make([]int,n)fori:=0;i<n;i++{fmt.Fscan(in,&pos[i])}sort.Ints(pos)ans:=0i:=0// 贪心，放置在中间fori<n{ans++left:=pos[i]mid:=pos[i]i++fori<n&&pos[i]-left<=m{mid=pos[i]i++}fori<n&&pos[i]-mid<=m{i++}}fmt.Print(ans)}