最少拦截系统 (贪心算法)_民生

最少拦截系统 (贪心算法)

admin

2024-02-24 22:31:29

0次

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

Input

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

Output

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

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

思路：

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

高度最大为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通信机制（服务）

热门资讯

122.（leaflet篇）l... 听老人家说：多看美女会长寿地图之家总目录（订阅之前建议先查看该博客）文章末尾处提供保证可运行...

育碧GDC2018程序化大世界... 1.传统手动绘制森林的问题采用手动绘制的方法的话，每次迭代地形都要手动再绘制森林。这...

Vue使用pdf-lib为文件... 之前也写过两篇预览pdf的，但是没有加水印，这是链接：Vu...

PyQt5数据库开发1 4.1... 文章目录前言步骤/方法 1 使用windows身份登录 2 启用混合登录模式 3 允许远程连接服...

Android studio ... 解决 Android studio 出现“The emulator process for AVD ...

Linux基础命令大全（上） ♥️作者：小刘在C站 ♥️个人主页：小刘主页 ♥️每天分享云计算网络运维...

再谈解决“因为文件包含病毒或潜... 前面出了一篇博文专门来解决“因为文件包含病毒或潜在的垃圾软件”的问题，其中第二种方法有...

南京邮电大学通达学院2023c... 题目展示一.问题描述实验题目1 定义一个学生类，其中包括如下内容：（1）私有数据成员 ①年龄 ...

PageObject 六大原则 PageObject六大原则： 1.封装服务的方法 2.不要暴露页面的细节 3.通过r...

【Linux网络编程】01：S... Socket多进程 OVERVIEWSocket多进程1.Server2.Client3.bug&...

数据结构刷题（二十五）：122... 1.122. 买卖股票的最佳时机 II思路：贪心。把利润分解为每天为单位的维度,然后收...

浏览器事件循环事件循环浏览器的进程模型何为进程？程序运行需要有它自己专属的内存空间࿰...

8个免费图片/照片压缩工具帮您... 继续查看一些最好的图像压缩工具，以提升用户体验和存储空间以及网站使用支持。无数图像压...

计算机二级Python备考（2... 目录一、选择题 1.在Python语言中： 2.知识点二、基本操作题 1. j...

端电压相电压线电压记得刚接触矢量控制的时候，拿到板子，就赶紧去测各种波形，结...

如何使用Python检测和识别... 车牌检测与识别技术用途广泛，可以用于道路系统、无票停车场、车辆门禁等。这项技术结合了计...

带环链表详解目录一、什么是环形链表二、判断是否为环形链表 2.1 具体题目 2.2 具体思路 2.3 思路的...

【C语言进阶：刨根究底字符串函... 本节重点内容：深入理解strcpy函数的使用学会strcpy函数的模拟实现⚡strc...

Django web开发(一)... 文章目录前端开发1.快速开发网站2.标签2.1 编码2.2 title2.3 标题2.4 div和s...

最少拦截系统 (贪心算法)

相关内容

热门资讯