首页
登录
从业资格
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的
admin
2022-08-02
3
问题
在一条笔直公路的一边有许多房子,现要安装消防栓,每个消防栓的覆盖范围远大于房子的面积,如下图所示。现求解能覆盖所有房子的最少消防栓数和安装方案(问题求解过程中,可将房子和消防栓均视为直线上的点)。该问题求解算法的基本思路为:从左端的第一栋房子开始,在其右侧m米处安装一个消防栓,去掉被该消防栓覆盖的所有房子。在剩余的房子中重复上述操作,直到所有房子被覆盖。算法采用的设计策略为( );对应的时间复杂度为(请作答此空)。
假设公路起点A的坐标为0,消防栓的覆盖范围(半径)为20米,10栋房子的坐标为(10,20,,30,35,60,80,160,210,260,300),单位为米。根据上述算法,共需要安装( )个消防栓。以下关于该求解算法的叙述中,正确的是( )。A.O(lgn)B.O(n)C.(nlgn)D.O(n2)
选项
A.O(lgn)
B.O(n)
C.(nlgn)
D.O(n2)
答案
B
解析
快速排序由C.A.R.Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序采用的思想是分治思想。贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。整个算法的时间复杂度是O(nlogn)。场地上可以安排活动1、8、11为一个场地;活动2、6、9一个场地;活动3为一个场地;活动4、7为一个场地;活动5、10为一个场地,共5个场地。
转载请注明原文地址:https://tihaiku.com/congyezige/2425195.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
针对组织内部的具体问题,在较小范围内和较短时间内实施的计划属于A.指令性计划
用于表示较短时间和小范围内医院感染的暴发或流行情况的指标是A.医院感染患病率B.
正常成人颅内压的范围是A.20~30mmHO B.50~100mmHO C.
3岁小儿身长95cm,体重15kg,牙20个,属于A.体重、身长超过正常范围
若分页系统的地址结构如下图所示。 该系统页的大小为()字节,页号的取值范围
话音信道的频率范围为300~3400Hz,如果采用PCM编码技术,则采样频率必须
无线城域网标准IEEE802.16规定的有效覆盖范围最大可达()。A.2km
若计算机字长为8,则采用原码表示的整数范围为-127~127,其中,()占用
扩展访问控制列表的编号范围是()。如果允许来自子网172.16.0.0/16
扩展访问控制列表的编号范围是()。如果允许来自子网172.16.0.0/16
随机试题
Newspapersarenotnearlyaspopulartodayastheywereinthepast.Therear
ThreeEnglishdictionariespublishedrecentlyalllayclaimtopossessinga
属于装饰工程现场深化设计师个人专业能力的要求有()。A.必须具备基本的室内设计
蜡在高温时融化,沥青黏度和温度敏感性的变化规律是()。A.沥青黏度降低,减小温
货币供给是( )以满足其货币需求的过程。A.中央银行向经济主体供给货币 B.
西红花的主产地为A.西班牙及希腊 B.马来西亚、印尼 C.越南、柬埔寨
农业生产及其服务设施用地在选址和布置时应做到()。A.农机站、农产品加工厂等
2020年全国实用新型专利申请授权中,下半年非职务专利申请授权数约是上半年的
问题行为与差生,后进生等问题学生的概念相同。()
男,67岁。反复咳嗽、咳痰、喘息5年,再发加重1周。查体:嗜睡,口唇发绀。两肺可
最新回复
(
0
)