导弹拦截(贪心策略)

2024-04-12 18:48
文章标签 拦截 贪心 策略 导弹

本文主要是介绍导弹拦截(贪心策略),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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个系统
}

这篇关于导弹拦截(贪心策略)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/897947

相关文章

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

SpringRetry重试机制之@Retryable注解与重试策略详解

《SpringRetry重试机制之@Retryable注解与重试策略详解》本文将详细介绍SpringRetry的重试机制,特别是@Retryable注解的使用及各种重试策略的配置,帮助开发者构建更加健... 目录引言一、SpringRetry基础知识二、启用SpringRetry三、@Retryable注解

MySQL 分区与分库分表策略应用小结

《MySQL分区与分库分表策略应用小结》在大数据量、复杂查询和高并发的应用场景下,单一数据库往往难以满足性能和扩展性的要求,本文将详细介绍这两种策略的基本概念、实现方法及优缺点,并通过实际案例展示如... 目录mysql 分区与分库分表策略1. 数据库水平拆分的背景2. MySQL 分区策略2.1 分区概念

springboot filter实现请求响应全链路拦截

《springbootfilter实现请求响应全链路拦截》这篇文章主要为大家详细介绍了SpringBoot如何结合Filter同时拦截请求和响应,从而实现​​日志采集自动化,感兴趣的小伙伴可以跟随小... 目录一、为什么你需要这个过滤器?​​​二、核心实现:一个Filter搞定双向数据流​​​​三、完整代码

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Deepseek使用指南与提问优化策略方式

《Deepseek使用指南与提问优化策略方式》本文介绍了DeepSeek语义搜索引擎的核心功能、集成方法及优化提问策略,通过自然语言处理和机器学习提供精准搜索结果,适用于智能客服、知识库检索等领域... 目录序言1. DeepSeek 概述2. DeepSeek 的集成与使用2.1 DeepSeek API

Redis的数据过期策略和数据淘汰策略

《Redis的数据过期策略和数据淘汰策略》本文主要介绍了Redis的数据过期策略和数据淘汰策略,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录一、数据过期策略1、惰性删除2、定期删除二、数据淘汰策略1、数据淘汰策略概念2、8种数据淘汰策略

SpringBoot中的404错误:原因、影响及解决策略

《SpringBoot中的404错误:原因、影响及解决策略》本文详细介绍了SpringBoot中404错误的出现原因、影响以及处理策略,404错误常见于URL路径错误、控制器配置问题、静态资源配置错误... 目录Spring Boot中的404错误:原因、影响及处理策略404错误的出现原因1. URL路径错