贪心算法(思路)

news/2024/2/23 16:22:23/文章来源:https://blog.csdn.net/Colinnian/article/details/135513855

最近在cf上做了很多贪心的题,写篇博客来总结一下

Problem - C - Codeforces

看第一道题

不难看出,我们需要在数组中找到一段奇偶相间的序列,要使他们的和最大, 在图中我们假设[1,2]和[3,4]是奇偶相间的序列,我们在在这两段序列中找到一段连续的子序列使其和最大,首先我们要处理这两段序列之间的过渡,也就是我们如何从1到2跳转到3到4,这个好办,看看2到3这段序列的性质,一个奇数减去一个奇数剩下一个偶数,一个偶数减去一个偶数剩下的也是一个偶数,所以,如果是奇数与奇数或是偶数与偶数相邻,我们只需要加上(a[i]-a[i-1])%2==0这个条件就可以把它筛选出来了,但这个条件必须配上i使用,当i=0的时候i-1数组就会越界,如果我们在(a[i]-a[i-1])%2==0这个条件前面放一个i,就像这样i&&(a[i]-a[i-1])%2==0,当i==0的时候就会结束,不会进行下一个条件的判断。

我们再来看下一个问题,如何在[1,2]和[3,4]中找到和最大的子连续序列,这一步其实是为了证明贪心可行性,来思考一下什么时候我们要抛弃上一个子序列而选择下一个子序列,当上一个子序列和为负数的时候我们是不是要另开一个子序列,假设总序列为3 2 -9 4 5,我们发现3+2-9是负数了,如果我们选择把3 2 -9 4 5全都加起来,是不是会对4 5这个序列不利,既然是负的贡献,我们不妨把它抛弃掉只取4 5,这时候我们发现3+2-9<0的,给定一个变量suf我们直接取suf=std::max(suf,0)+a[i](a[i]是当前这个数组的元素)即可,这时我们会遇到一种情况,假如序列是17 4 -29 6 1怎么办,明显17+4要大于6+1,所以这是我们还需要一个变量ans用来记录前面的最大值就可以解决这个问题了

using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}int ans = -1E9;int suf = -1E9;for (int i = 0; i < n; i++) {if (i && (a[i] - a[i - 1]) % 2 == 0) {suf = 0;}suf = std::max(suf, 0) + a[i];ans = std::max(ans, suf);}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}

所以这种贪心适合于在一个数组里,存在很多段符合规律的子段,我们需要在子段里找到满足要求的子子段,通常是和最小或者最大和。这道题是局部最优找全局最优

可以总结出一个模版如下

int ans = -1E9;
int suf = -1E9;
for (int i = 0; i < n; i++) {if (i && 条件) {suf = 0;}suf = 用于积累;ans = 不断取更合适的子子区间;
}

 

Poblem - C - Codeforcese

而这道题是为了找出每一个全局最优,可以发现当(ai+aj)/2*2 ai和aj一个为奇数一个为偶数的时候才会产生运算后的结果比运算前的结果小1的效果,只有偶数的时候不可能产生奇数,而只有奇数的时候却可以产生偶数,进而产生-1的效果,所以当i为奇数的时候,masha会优先合成两个奇数,i为偶数的时候olya会将一个奇数和一个偶数合成,由于玛莎是先手,所以在olya的回合必定会存在偶数,所以我们可以发现每消耗3个奇数就可以产生一个-1,所以就相当于分配m个奇数,i=1玛莎会消耗2,i=2,olya会消耗1,以此类推,也就是说当我们消耗完3个奇数,下一次被分配必定是玛莎,所以只需要用m/3就可以知道有多少个-1产生,那么m%2=2的时候,此时还剩下两个奇数,刚好分配给玛莎不会产生-1,m%3=1时,只剩下一个奇数了,玛莎不得不合成奇数和偶数产生-1。

using i64 = long long;
void solve() {int n;std::cin >> n;i64 sum = 0;int odd = 0;for (int i = 1; i <= n; i++) {int a;std::cin >> a;sum += a;odd += a % 2;int res;if (odd == 1 && i == 1)res = 0;else {res = odd / 3;if (odd % 3 == 1) {res += 1;}}std::cout << sum - res << " \n"[i == n];}}
int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t;std::cin >> t;while (t--) {solve();}return 0;
}

所以代码如下,odd用于累加,res用于跟进最大值。 

Problem - E - Codeforces

这个E其实也是一个累加问题,E我之前写过一次题解cf918div4的E题讲解-CSDN博客 

大家自己看一下吧,总的来说就是从局部最优到全局最优的过程 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925247.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Docker】数据卷挂载以及宿主机目录挂载的使用

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《Docker实战》。&#x1f3af;&#x1f3af; &…

docker部署私人云盘nextcloud

首先查看效果 1.拉取镜像 docker pull nextcloud 2.创建目录 mkdir -p /data/nextcloud/{config,data,apps} 3.创建实例 docker run -itd --name yznextcloud -v /data/nextcloud/config:/var/www/html/config -v /data/nextcloud/data:/var/www/html/data -v /data/nextc…

关于html导出word总结一

总结 测试结果不理想&#xff0c;html-to-docx 和 html-docx-js 最终导出的结果 都 差强人意&#xff0c;效果可以见末尾的附图 环境 "electron": "24.3.0" 依赖库 html-docx-js html-docx-js - npm html-to-docx html-to-docx - npm file-saver…

基于DNA的密码学和隐写术综述

摘要 本文全面调研了不同的脱氧核糖核酸(DNA)-基于密码学和隐写术技术。基于DNA的密码学是一个新兴领域,利用DNA分子的大规模并行性和巨大的存储容量来编码和解码信息。近年来,由于其相对传统密码学方法的潜在优势,如高存储容量、低错误率和对环境因素的抗性,该领域引起…

JDK8-JDK17版本升级

局部变量类型推断 switch表达式 文本块 Records 记录Records是添加到 Java 14 的一项新功能。它允许你创建用于存储数据的类。它类似于 POJO 类&#xff0c;但代码少得多&#xff1b;大多数开发人员使用 Lombok 生成 POJO 类&#xff0c;但是有了记录&#xff0c;你就不需要使…

第 2 章 数据结构和算法概述

文章目录 2.1 数据结构和算法的关系2.2 看几个实际编程中遇到的问题2.2.1 问题一-字符串替换问题2.2.2 一个五子棋程序2.2.3 约瑟夫(Josephu)问题(丢手帕问题)2.2.4 其它常见算法问题: 2.3 线性结构和非线性结构2.3.1 线性结构2.3.2 非线性结构 2.1 数据结构和算法的关系 数据 …

使用Qt连接scrcpy-server控制手机

Qt连接scrcpy-server 测试环境如何启动scrcpy-server1. 连接设备2. 推送scrcpy-server到手机上3. 建立Adb隧道连接4. 启动服务5. 关闭服务 使用QTcpServer与scrcpy-server建立连接建立连接并视频推流完整流程1. 开启视频推流过程2. 关闭视频推流过程 视频流的解码1. 数据包协议…

【STM32】HAL库的STOP低功耗模式UART串口唤醒,第一个接收字节出错的问题(已解决)

【STM32】HAL库的STOP低功耗模式UART串口唤醒&#xff0c;第一个接收字节出错的问题&#xff08;已解决&#xff09; 文章目录 BUG复现调试代码推测原因及改进方案尝试中断时钟供电外设唤醒方式校验码硬件问题 切换到STOP0模式尝试结论和猜想解决方案附录&#xff1a;Cortex-M…

js动态设置关键侦@keyframes

js动态设置关键侦keyframes 1.前置知识 关键侦keyframes规则通过在动画序列中定义关键侦的样式来控制CSS动画序列的中间步骤 keyframes slidein {from {transform: translateX(0%);}to {transform: translateX(100%);} } // from 等价于 0%&#xff1b;to 等价与 100% // 或…

【已解决】C语言进行多线程数据切割查找数据

第一次听到多线程切割&#xff0c;笔者也没听的太懂&#xff0c;但发现多线程数据切割其实就是分出多个线程&#xff0c;进行处理查找数据的事情。而为什么切割呢&#xff0c;就是因为数据不够线程数分的&#xff0c;假如1k个数据&#xff0c;7个线程&#xff0c;这里不能够整除…

RabbitMQ的安装使用

RabbitMQ是什么&#xff1f; MQ全称为Message Queue&#xff0c;消息队列&#xff0c;在程序之间发送消息来通信&#xff0c;而不是通过彼此调用通信。 RabbitMQ 主要是为了实现系统之间的双向解耦而实现的。当生产者大量产生数据时&#xff0c;消费者无法快速消费&#xff0c;…

蓝桥杯备赛 | 洛谷做题打卡day5

蓝桥杯备赛 | 洛谷做题打卡day5 图论起航&#xff0c;一起来看看深&#xff08;广&#xff09;度优先吧 ~ 文章目录 蓝桥杯备赛 | 洛谷做题打卡day5图论起航&#xff0c;一起来看看深&#xff08;广&#xff09;度优先吧 ~【深基18.例3】查找文献题目描述 输入格式输出格式样例…

vue知识-04

计算属性computed 注意&#xff1a; 1、计算属性是基于它们的依赖进行缓存的 2、计算属性只有在它的相关依赖发生改变时才会重新求值 3、计算属性就像Python中的property&#xff0c;可以把方法/函数伪装成属性 4、computed: { ... } 5、计算属性必须要有…

MySQl Mybatis

一、MySQL 1.1 概述 1.1.1 MySQL安装 1.1.2 数据模型 1.1.3 SQL简介 1.2 DDL 1.2.1 数据库操作 1.2.2 图形化工具 1.2.3 表结构操作 &#xff08;一&#xff09;创建 &#xff08;二&#xff09;数据类型 &#xff08;1&#xff09;数值类型 age tinyint unsigned——加上…

Kubernetes 集群管理—日志架构

日志架构 应用日志可以让你了解应用内部的运行状况。日志对调试问题和监控集群活动非常有用。 大部分现代化应用都有某种日志记录机制。同样地&#xff0c;容器引擎也被设计成支持日志记录。 针对容器化应用&#xff0c;最简单且最广泛采用的日志记录方式就是写入标准输出和标…

书生·浦语大模型--第三节课笔记--基于 InternLM 和 LangChain 搭建你的知识库

文章目录 大模型开发范式RAGLangChain框架&#xff1a;构建向量数据库构建检索问答链优化建议web 部署 实践部分环境配置 大模型开发范式 LLM的局限性&#xff1a;时效性&#xff08;最新知识&#xff09;、专业能力有限&#xff08;垂直领域&#xff09;、定制化成本高&#…

测试平台出问题?看我20分钟快速定位!

今天遇到一个问题&#xff0c;感觉挺有意思&#xff0c;处理过程也非常有意义&#xff0c;希望能给大家一个借鉴吧。今天一位小姐姐找到了我们大组长&#xff0c;说测试平台添加自动化测试用例失败&#xff0c;之后我们组长把我拉到了一个群里让我去看一下&#xff0c;硬着头皮…

C++面试宝典第19题:最长公共前缀

题目 编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀,返回空字符串""。说明:所有输入只包含小写字母a-z。 示例1: 输入: ["flower", "flow", "flight"]输出: "fl" 示例2: 输入: ["dog",…

如何在Windows 10/11的防火墙中禁止和允许某个应用程序,这里提供详细步骤

想阻止应用程序访问互联网吗&#xff1f;以下是如何通过简单的步骤阻止和允许Windows防火墙中的程序。​ 一般来说&#xff0c;大多数用户永远不需要担心应用程序访问互联网。然而&#xff0c;在某些情况下&#xff0c;你需要限制应用程序访问互联网。 例如&#xff0c;有问题…

vue知识-03

购物车案例 要实现的功能&#xff1a; 1、计算商品总价格 2、全选框和取消全选框 3、商品数量的增加和减少 <body> <div id"app"><div class"row"><div class"col-md-6 col-md-offset-3"><h1 class"text-center…