导弹拦截(贪心策略)_okouk的博客-程序员宅基地

在这里插入图片描述
题目分析

noip老经典贪心问题了
使用贪心策略,现在对于导弹i,和已经存在的k个系统,导弹i现在面临两种情况。
1、加入已存在的k个系统之中的一个系统之中。
当然前提条件是至少比其中一个系统的最小值小,那么如何用更少的系统,去装下更多的导弹呢?导弹i当然要选择能加入的导弹最小值的距离最近的,这样系统里的导弹才能更加的紧凑,不浪费空间。局部贪心导致最优解。
2、无法加入已存在的任何一个系统
新开辟一个系统。

code:

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int arr[1005];
int l[1005];
int main()
{
    
	//导弹拦截的贪心策略
	//首先选取第一个导弹为第一组的最低拦截度 
	//之后导弹只能比其更低
	int x,k=1,n=0;
	while (cin >> x)
	{
    
		arr[++n] = x;
	}
	l[k] = arr[1];
	for (int i = 2; i <= n; i++)
	{
    
		int p = 0;//导弹安家指针 遍历所有的导弹拦截设备
		for (int j = 1; j <= k; j++)
		{
    
			if (l[j] >= arr[i])//i个导弹能够放进去
			{
    
				if (p == 0)
				{
    
					p = j;//这个地方先标记
				}
				else if (l[j]< l[p])//选取最小的 选取与i个导弹最接近的
				{
    
					p = j;
				}
			}
		}
		if (p == 0)//i没有能放入某一堆的
		{
    
			l[++k] = arr[i];//放下个去
		}
		else
		{
    
			l[p] = arr[i];//放进刚刚标记的系统里面
		}
	}
	cout << k;//输出k个系统
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/TKKDOUZI/article/details/108968650

智能推荐

Map使用中的问题 异常java.util.ConcurrentModificationException_码说AI的博客-程序员宅基地

我想对数据访问做一个缓冲,选用Map来做缓冲容器,考虑到效率我选择了HashMap 想想循环往里面仍或者更新数据,那么当系统不访问的时候这些内容,我应该实时的清除这些内存内容 根据需要,我写了一个静态Map做内存容器,然后设置一个Spring定时器来定时检查和处理那些数据需要清除但是定时器处理时遇到异常 java.util.ConcurrentModific

第二十三章 : 打印_砖业洋__的博客-程序员宅基地

打印After spending the last couple of chapters manipulating text, it’s time to put that text on paper. In this chapter, we’ll look at the command-line tools that are used to print files and control prin...

Feign简介与简单应用_chengqiuming的博客-程序员宅基地_feign

一 点睛Feign是Netflix开发的声明式、模板化的HTTP客户端, Feign可以帮助我们更快捷、优雅地调用HTTP API。在Spring Cloud中,使用Feign非常简单——创建一个接口,并在接口上添加一些注解,代码就完成了。Feign支持多种注解,例如Feign自带的注解或者JAX-RS注解等。Spring Cloud对Feign进行了增强,使Feign支持了Sprin...

ArcGIS布局视图(Layout)大小设置_fantasy云桓的博客-程序员宅基地_arcgis更改布局视图框大小

要在文件里面选择页面和打印设置,选择自定义,然后设置宽度和高度

随便推点

Vue源码阅读(24):v-on 指令的源码解析_纷飞丿的博客-程序员宅基地_v-on原理

今天讲讲 v-on 指令的底层实现原理。在 Vue 中,v-on 指令有两种用法,第一种是将 v-on 指令使用在自定义组件上,例如:&lt;my-component v-on:myEvent="doSomething"&gt;&lt;/my-component&gt;,使用 v-on 指令监听了组件的 myEvent 事件,回调函数是doSomething,当在组件中执行 this.$emit('myEvent') 时,会触发执行 doSomething 函数,有没有发现这和我上一篇文章中的 vm.$o.

ARM裸板开发:07_IIC 通过IIC总线接口读写时钟芯片时间参数实现的总结_weixin_34024034的博客-程序员宅基地

问题一:程序直接在iRAM内部可正常执行,而程序搬移(Nand -&gt;SDRAM)之后,就不能正常运行了#define NAND_SECTOR_SIZE 2048 /* 读函数 */void nand_read(unsigned char *buf, unsigned long start_addr, int size){ int i, j; ...

剑指Offer——8.二叉树的下一个节点_BlackMaBa的博客-程序员宅基地

题目:给定一颗二叉树和其中一个节点,如何找出中序遍历序列的下一个节点?树中的节点除了有两个分别指向左、右子节点的指针,还有一个指向父节点的指针。二叉树节点定义如下: class BinaryTreeNode { int data; BinaryTreeNode left; BinaryTreeNode right; B...

springboot--支付宝条码支付的实现_Edwina414的博客-程序员宅基地

这几天一直在调支付宝的条码支付的接口,遇到不少问题,想跟大家分享一下。我还是建议大家在官网下载的接口先调通了,再放入自己的项目中。我的小伙伴做的是微信条码支付,不得不说,支付宝的接口文档比微信的详细多了,此外支付宝还附带一个样例demo,非常便于新手开发与学习       所谓的条码支付,就是商家扫用户的付款二维码进行结账,用户只需展示付款二维码即可。而扫码支付是用户扫商家的二维码,然后输入金

深入解读微服务架构下分布式事务解决方案_蔚1的博客-程序员宅基地

微服务倡导将复杂的单体应用拆分为若干个功能简单、松耦合的服务,这样可以降低开发难度、增强扩展性、便于敏捷开发。概念一经提出迅速火遍全球。当前 Hailo 有160个不同服务构成,NetFlix 有大约600个服务。国内方面,阿里巴巴、腾讯、360、京东、58同城等很多互联网公司都进行了微服务化实践。分布式事务问题被著名架构师 Chris Richardson 称为微服务的三大难题之一,而且当前 D...

php级联删除怎么做,MSSQL_SQL 级联删除与级联更新的方法,复制代码 代码如下:on delete casc - phpStudy..._weixin_39876450的博客-程序员宅基地

on delete cascade当你更新或删除主键表时,那么外键表也会跟随一起更新或删除,需要在建表时设置级联属性CREATE TABLE Countries(CountryId INT PRIMARY KEY)INSERT INTO Countries (CountryId) VALUES (1)INSERT INTO Countries (CountryId) VALUES (2)INSER...