HDU1257 最少拦截系统 —— 贪心
2024-10-20 16:11:18
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1257
最少拦截系统
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 45924 Accepted Submission(s): 18118
Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
Source
Recommend
JGShining
题解:
1.对于当前导弹, 找到一套高度尽量小的系统,能够把它拦截。悟:用最小的代价去完成同一件事,以此保存最大的实力,即贪心的思想。
2.如果找不到能把当前导弹拦截的系统,那就只能搬出一套新的系统。
3.其实此题的解法就是贪心,与LIS无关,只是在优化“寻找拦截系统”的时候, 用到了二分查找, 然后写法就刚好与LIS 的 nlogn写法一样。个人认为是巧合。
写法一:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5; int use[maxn], a[maxn]; int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i = ; i<=n; i++)
scanf("%d",&a[i]); int cnt = ;
for(int i = ; i<=n; i++)
{
int k = -, minn = 2e9;
for(int j = ; j<=cnt; j++) //找到一套高度尽量小的系统,能够把当前导弹拦截住。
if(use[j]>a[i] && use[j]<minn)
minn = use[k = j]; if(k==-) //如果找不到,再搬出一个拦截系统
use[++cnt] = a[i];
else //如果找到, 则把当前导弹拦截,然后更新此系统的高度
use[k] = a[i];
}
printf("%d\n",cnt);
}
return ;
}
写法二:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5; int use[maxn], a[maxn]; int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{ for(int i = ; i<=n; i++)
scanf("%d",&a[i]); int cnt = ;
for(int i = ; i<=n; i++)
{
if(i== || a[i]>use[cnt]) //最高高度都不能把当前导弹拦截的系统, 则搬出一台新的系统。
use[++cnt] = a[i]; else //否则,找到一套高度尽量小的系统,能够把当前导弹拦截住,并且更新此系统的高度。
{
int id = lower_bound(use+,use++cnt,a[i]) - (use+);
use[id+] = a[i];
}
}
printf("%d\n",cnt);
}
return ;
}
最新文章
- Kali Linux additional tools setup
- Func<;T>;、Action<;T>; 的区别于说明
- linux中chmod更改文件权限命令
- iOS定位到崩溃代码行数
- a:link,a:visited,a:hover,a:active
- nginx系统真正有效的图片防盗链完整设置详解
- UDKtoUE4Tool-UDKUE3资源移植UE4工具
- linux - markdown编辑器
- MyEclipse中配置SWT/JFace/SWT-Designer 艰辛路程
- 什么是实时应用程序自我保护(RASP)?
- 常用的JavaScript正则匹配规则代码收藏,很实用
- string字母排序,
- 分享一个3D球面标签云
- Django学习(四) Django提供的后台管理系统以及如何定义URL路由
- UNIX网络编程——UDP编程模型
- [JAVA]JAVA实现多线程的三种方式
- 苹果中国全系降价:iphone最高降500元,用户可退差价
- Oracle 中的一些重要V$ 动态性能视图,系统视图和表
- jvm系列四、jvm知识点总结
- mysql中的用法 count group by having
热门文章
- Leetcode 309.最佳买卖股票时机含冷冻期
- php引入PHPMailer发送邮件
- NYOJ-676小明的求助,快速幂求模,快速幂核心代码;
- SQL Server 创建唯一约束sql语句
- 【Educational Codeforces Round 48】
- Es首页
- HDU 1028 整数拆分 HDU 2082 找单词 母函数
- Palindrome--poj 1159(最长公共子字符串+滚动数字)
- MongoDB学习day09--Mongoose数据校验
- Java日志框架使用技巧收集(slf4j、jcl、jul、log4j1、log4j2、logback)