描述
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。怎么办呢?请帮助计算一下最少需要多少套拦截系统?
输入
输入若干组数据(不超过100组),每组数据一行,分别为:导弹总个数(正整数,不超过1000),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
输出
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例输入
8 389 207 155 300 299 170 158 65
样例输出
2
#include <stdio.h>
#include <stdlib.h>
int missle[1000];
int sys[1000];
int find(int, int);
int compare(const void * a, const void * b)
{
return (*(int *)a - *(int *)b);
}
int main()
{
int n;
while(scanf("%d", &n) == 1)
{
int j = 0;
int i;
int a = 1;
for(i = 0; i < n ; i++)
{
scanf("%d", &missle[i]);
}
sys[0] = missle[0];
for(i = 1; i < n; i++)
{
int pos = find(i, a);
if(pos == -1)
{
a++;
sys[a-1] = missle[i];
}
}
printf("%d\n", a);
}
return 0;
}
int find(int spos, int a)
{
int pos = -1;
int i;
for(i = 0; i < a; i++)
{
if( missle[spos] <= sys[i])
{
pos = i;
sys[i] = missle[spos];
break;
}
}
qsort(sys, a, sizeof(int), compare);
return pos;
}
分享到:
相关推荐
采用贪心策略,首先把第一枚导弹的高度存入数组中,意味着要使用第一套拦截系统,然后如果第二枚导弹的高度大于第一枚的话(不能拦截),把第二枚的高度加入数组中(第一枚之后),需要增加另一套拦截系统,如果小于...
主要介绍了Android中利用Xposed框架实现拦截系统方法的相关资料,需要的朋友可以参考下
一流信息监控拦截系统免费版 网络信息监控拦截
API HOOK拦截系统窗口,采用APIHOOK技术对系统API函数MessageBox进行拦截,让系统执行自定义的函数内容!
拦截android系统异常,自己定义弹出的异常信息
问题背景:某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够...表示:这套系统最多能拦截 M 枚导弹,如果要拦截所有导弹最少要配备 N 套这种导弹系统。
4、拦截指定的URL连接,如,BBS页面拦截、或根据预先设定的目录名称进行拦截,如 /*.asp/ 等目录名称; 5、限制HTTP动作,如,限制只允许POST/GET/HEAD等动作,其他PUT等动作进行拦截; 6、限制指定IP地址(IP...
基于PyQt5实现的邮件拦截系统、视频播放器、以及pyqt5的学习笔记 资源内包含两个项目:邮件拦截系统、视频播放器,以及完整的pyqt学习笔记,相关技术总结,非常详细。 基于PyQt5实现的邮件拦截系统、视频播放器、...
基于PyQt5实现的邮件拦截系统、视频播放器、以及pyqt5的学习笔记.zip 基于PyQt5实现的邮件拦截系统、视频播放器、以及pyqt5的学习笔记.zip 基于PyQt5实现的邮件拦截系统、视频播放器、以及pyqt5的学习笔记.zip 基于...
用户层下拦截系统api的原理与实现.txt 用户层下拦截系统api的原理与实现.txt 用户层下拦截系统api的原理与实现.txt 用户层下拦截系统api的原理与实现.txt
生态拦截系统设计.pdf
驱动级Hook拦截系统内核调用,源码 驱动级Hook拦截系统内核调用,源码
采用SSH进行开发,使用Spring的AOP对目标进行拦截,有效的控制权限。
Windows系统API函数拦截技术研究
易语言源码易语言拦截系统消息例程源码.rar 易语言源码易语言拦截系统消息例程源码.rar 易语言源码易语言拦截系统消息例程源码.rar 易语言源码易语言拦截系统消息例程源码.rar 易语言源码易语言拦截系统消息例程...
系统返回按钮事件拦截 Swift 版本
通过重载虚函数WndProc在C#下处理Windows系统消息。
闪灵短链接系统|闪灵微信QQ域名防拦截系统是一款以php+MySQL进行开发的短网址在线生成系统源码。 功能介绍: 1.可将长网址自动缩短为短网址,方便记忆和使用。 2.短网址默认为临时有效,可付费升级为永久有效,接...
闪灵短域名–微信QQ域名防拦截系统是一款以php+MySQL进行开发的短网址在线生成系统源码。 功能介绍: 1.可将长网址自动缩短为短网址,方便记忆和使用。 2.短网址默认为临时有效,可付费升级为永久有效,接入支付后可...