最少拦截系统 (贪心算法)
admin
2024-02-24 22:31:29
0次

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

2

思路：

建立一个数组，记录已经投入使用的导弹拦截系统当前拦截上限，

高度最大为30000的正整数，最多每个一米一个系统，所以开30005的

数组足够了，为了使得使用的拦截系统最少，自然是要考虑使用与当前高度最

接近的系统拦截（应该是贪心算法）；如果所有系统的高度均小于导弹的高度，

则增加拦截系统

代码：

#include
#define MAX 30005
#define Inf 0x3f3f3f3f
#include
#include
using namespace std;
int n,cnt;
int dp[MAX];//记录每套拦截系统当前可以达到的最大高度
int main(){while(scanf("%d",&n)!=EOF){memset(dp,0,sizeof(dp));cnt=0;int i,j,h;for(i=0;i=h&&dp[j]-h
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：git clone后修改文件然后再上传覆盖

下一篇：六、ROS2通信机制（服务）

相关内容

热门资讯

我的电脑双击打不开图片-绝望深... 我是一台电脑，虽然我在这个数字世界中扮演着重要的角色，但是有时候我也会遇到一些棘手的问题。最近，我陷...
省电宝下载-省电宝：智能手机用... 省电宝是一款专为智能手机用户打造的应用程序，旨在帮助用户最大限度地延长手机电池寿命。作为一名手机用户...
万能恢复大师5破解版-一键恢复... 你是否曾经因为误操作、病毒攻击或者硬件故障而丢失了重要的数据？你是否曾经为找回这些数据而焦头烂额？别...
linux用户管理图形工具-L... 作为一名校长，我每天都要面对繁琐的学生管理工作。而在这个数字化时代，学生们对于电脑的依赖程度也越来越...
七喜吧 福利社区-七喜吧福利社... 欢迎来到七喜吧福利社区！这里是一个为大家提供丰富多彩福利的社区。无论你是想找到最新的优惠活动，还是想...
wuaucltexe-开放自由... ，是一种神奇的存在。它可以让你感受到无限的乐趣和刺激，同时也能带给你意想不到的收获和成就感。在的世界...
cad怎么显示坐标系-CAD设... 在CAD设计中，坐标系是一个非常重要的概念。它是用来确定物体在空间中位置和方向的参考系统，为设计和制...
急性血癌能活多久-急性血癌：生... 急性血癌，是一种威胁生命的疾病。当诊断结果揭示出这个残酷的事实时，人们心中充满了无尽的恐惧和不安。然...
3s技术的应用-智能简约的思越... 一、3s技术的定义和原理3s技术，全名Smart, Speedy, and Simple Techn...
eazyrecover注册码-... 大家好，我是李老师，一个热爱技术的IT专家。今天我要给大家介绍一款非常实用的工具——eazyreco...
小米手机清除数据恢复-数据意外... 在现代社会中，手机已经成为人们生活中不可或缺的一部分。而小米手机作为其中的佼佼者，凭借其性能优越和稳...
ecognition安装教程-... 欢迎各位同学来到这个充满创新和想象力的世界！在这里，我们将带你一起探索ecognition的安装教程...
c16009课后测验100分-... 学习不仅仅是上课听讲，更要勤做课后测验！ c16009课后测验100分就是你的目标！在课堂上，我们认...
感冒后老是咳嗽怎么办-感冒过去... 感冒后老是咳嗽怎么办？这简直是折磨人的问题！每次感冒过去了，却总有一股顽固的咳嗽缠绕着我，让我无法好...
netware-网络软件系统核... 在这个快速发展的数字化时代，互联网已经成为了我们生活中不可或缺的一部分。而在互联网的背后，有着一个庞...
手机dcim-手机DCIM：记... 手机DCIM是手机存储照片和视频的文件夹，它承载着我们生活的点滴和回忆。这个小小的文件夹，却拥有着无...
extremecopy注册码-... 在这个快节奏的时代，我们常常会被各种信息冲击得晕头转向。每天都有大量的文字、图片、视频涌入我们的视野...
身份证号码计算-身份证号码之谜... 在这个数字化的时代，数字无处不在，我们的生活也被数字所主导。然而，在数字的海洋中，还隐藏着一些神秘的...
大便出鲜血严重吗-大便出血：严... 血，是生命的气息。当它们在身体中的通道上出现，我们应该引起足够的重视。然而，大便出鲜血并不总是意味着...
什么空调节能省电-炎炎夏日，空... 夏天到了，热浪滚滚，空调成了我们最亲密的伙伴。但是，你知道吗？只要降低室内温度1摄氏度，就能节省10...