登入帳戶　 |　訂單查詢　 |　購物車/收銀台(0)　|　在線留言板　 |　付款方式　 |　聯絡我們　 |　運費計算　 |　幫助中心　|　 加入書簽
	全部範圍 - 圖書 - 　- 中文簡體書(大陸書) - 　- 英文書（原版） - - 音碟 - 　- 音樂 - 　- 影視 - - 雜誌 - 全文 精確	會員登入   新用戶註冊

HOME新書上架暢銷書架好書推介特價區會員書架精選月讀2023年度TOP分類閱讀雜誌

香港／國際用戶

最新/最熱/最齊全的簡體書網

品種：超過100萬種書，正品正价，放心網購，悭钱省心

送貨：速遞 / 物流，時效：出貨後2-4日

新書推薦： 《 数据有道：数据分析+图论与网络+微课+Python编程（鸢尾花数学大系：从加减乘除到机器学习） 》 售價：NT$ 1214.0 《 500万次倾听：陪伤心的人聊聊 》 售價：NT$ 245.0 《 英国商业500年（见证大国崛起与企业兴衰，启迪未来商业智慧。） 》 售價：NT$ 367.0 《 万千心理·儿童心理治疗中的心智化：临床实践指导 》 售價：NT$ 398.0 《 自我囚禁的人：完美主义的心理成因与自我松绑（破除你对完美主义的迷思，尝试打破自我评价过低与焦虑的恶性循环） 》 售價：NT$ 301.0 《 周易 》 售價：NT$ 203.0 《 东南亚的传统与发展 》 售價：NT$ 306.0 《 乾隆制造 》 售價：NT$ 398.0

編輯推薦： 这是一本“算法入门”书，写给“正在学或刚学过编程语言，但是数据结构、算法零基础”的初学者。 本书的读者符合这样的画像:刚学过编程语言，C/C 、Java、Python 这几种语言中的任何一个都可以;有基本的编码能力，语法比较熟悉;编过一些代码，但仍然不熟练;不懂数据结构和算法，遇到较难的问题没有思路。 这位勤奋的读者有以下目标: (１)数据结构和算法入门，建立计算思维。 (２)大量编码，提高编码能力。 (３)参加蓝桥杯大赛并获奖。 如果读者准备参加蓝桥杯全国软件和信息技术专业人才大赛(软件类)，看这本书正合适，因为题目大多是蓝桥杯大赛的真题，并且按照蓝桥杯大赛的要求进行了详细的解析。 本书也适用于准备其他算法竞赛，例如全国青少年信息学奥林匹克竞赛(NOI)、国际大学生程序设计竞赛(ICPC)、中国大学生程序设计竞赛(CCPC)、中国高校计算机大赛Ｇ团体程序设计天梯赛等，因为所有的算法竞赛的考点都是相通的。 用一句话概括本书的作用:通过本书的学习，读者可以从一名蓝桥杯、算法竞赛的小白，成长为掌握算法知识、建立算法思维、具备编码能力的专业的计算机编程人才。 內容簡介： 本书是面向蓝桥杯全国软件和信息技术专业人才大赛的软件类赛项（以下简称蓝桥杯软件类大赛）的入门图书，从数据结构和算法的维度帮助广大读者训练编程思维和计算思维，掌握编程方法和解题技巧。 　　本书共10章，第1章主要介绍了蓝桥杯软件类大赛的基本情况，归类汇总了其涉及的知识点（包括算法知识点），详细介绍了其在线评测系统以说明评分情况。第2~10章则由浅入深、由易到难地介绍了各类知识点，包括手算题和杂题、基础数据结构、基本算法、搜索、高级数据结构、动态规划、数学、字符串、图论等，对于每一类知识点都简明扼要地进行说明，并以真题作为例题进行细致讲解，以更好地帮助读者实现学用结合的学习效果。需要特别说明的是，本书例题的代码部分，分别由C 、Python、Java三种语言来实现（书中仅提供以C 、Python语言编写的代码，以Java语言编写的代码可从本书的配套数字资源中获取）。 　　本书不仅适合作为蓝桥杯软件类大赛参赛者的备赛用书，还适用于备赛其他编程或算法类大赛（如全国青少年信息学奥林匹克竞赛NOI、国际大学生程序设计竞赛ICPC、中国大学生程序设计竞赛CCPC、中国高校计算机大赛?团体程序设计天梯赛GPLT等）。此外，本书还可作为本科生和研究生的相关算法课程的教材或参考资料。 關於作者： 罗勇军，华东理工大学计算机系教师，担任华东理工大学程序设计竞赛主教练18年，指导学生参加世界大学生程序设计竞赛ICPC、中国大学生程序设计竞赛CCPC、蓝桥杯大赛，成绩优异，曾两次带队参加ICPC世界总决赛。2019年出版《算法竞赛入门到进阶》，荣获清华大学出版社2019、2020、2021年度畅销书。2022年出版《算法竞赛》，荣获清华大学出版社2022年度十佳图书，CSDN2022年度十大图书。2023年出版《程序设计竞赛专题挑战教程》，蓝桥杯大赛官方备赛书，人民邮电出版社2023年度畅销新书奖。 杨建国，华东理工大学信息科学与工程学院教师。带领学生参加ACM-ICPC 国际大学生程序设计竞赛、蓝桥杯全国软件和信息技术专业人才大赛、百度之星程序设计大赛、中国大学生程序设计竞赛CCPC，多次获得国赛一等奖，其中蓝桥杯大赛2020-2024年省赛获奖184项，国赛32项。学校蓝桥杯大赛、百度之星程序设计大赛负责人。主要研究信息安全。 目錄： 第1章蓝桥杯大赛软件类概述 1.1蓝桥杯软件赛的参赛规则 1.2蓝桥杯软件赛的题型介绍 1.3蓝桥杯软件赛的判题 1.4蓝桥杯软件赛的知识点 1.5备赛计划 第2章杂题和填空题 2.1杂题和编程能力 2.2输入与输出 2.3杂题例题 2.4填空题概述 2.5填空题例题 第3章数据结构基础 3.1数组与高精度 3.2STL概述 3.2.1String库 3.2.2迭代器 3.2.3容器概述 3.2.4vector 3.2.5算法函数概述 3.2.6set和map 3.3链表 3.3.1手写链表 3.3.2STL list 3.4队列 3.4.1手写队列 3.4.2STL queue 3.5优先队列 3.6栈 3.6.1手写栈 3.6.2STL stack 3.7二叉树 3.7.1二叉树的概念 3.7.2二叉树的存储和编码 3.7.3例题 3.8并查集 3.8.1并查集的基本操作 3.8.2路径压缩 3.8.3例题 3.9扩展学习 第4章排序和排列 4.1十大排序算法 4.1.1选择排序 4.1.2冒泡排序 4.1.3插入排序 4.1.4希尔排序 4.1.5计数排序 4.1.6桶排序 4.1.7基数排序 4.1.8归并排序 4.1.9快速排序 4.1.10堆排序 4.2排序函数 4.2.1STL的排序函数 4.2.2例题 4.3排列和组合 4.3.1手写全排列和组合 4.3.2全排列函数next_permutation() 4.3.3例题 第5章基本算法 5.1算法与算法复杂度 5.1.1算法的概念 5.1.2计算资源 5.1.3算法复杂度 5.2前缀和 5.2.1前缀和的概念 5.2.2例题 5.3差分 5.3.1一维差分 5.3.2二维差分 5.4二分 5.4.1二分法的经典应用 5.4.2例题 5.5贪心 5.5.1经典贪心问题 5.5.2例题 5.6扩展学习 第6章搜索 6.1DFS代码框架 6.2DFS常见应用 6.2.1DFS与排列组合 6.2.2DFS与连通性 6.3DFS剪枝 6.4DFS例题 6.5BFS基本代码 6.6BFS与最短路径 6.7BFS判重 6.8例题 6.9扩展学习 第7章数学 7.1模运算 7.2快速幂 7.3素数 7.3.1素数的判定 7.3.2素数筛 7.3.3质因数分解 7.4GCD和LCM 7.4.1GCD 7.4.2LCM 7.4.3例题 7.5扩展学习 第8章动态规划 8.1动态规划的概念 8.2动态规划的两种编码方法 8.3DP设计基础 8.4DP背包 8.4.10/1背包 8.4.2完全背包 8.4.3分组背包 8.4.4背包相关问题 8.5DP例题 8.6扩展学习 第9章图论 9.1图的存储 9.2最短路径算法 9.2.1Floyd算法 9.2.2BellmanFord算法 9.2.3Dijkstra算法 9.3最小生成树 9.3.1Prim算法 9.3.2Kruskal算法 9.4扩展学习 內容試閱： 经过十多年的发展，蓝桥杯大赛已经成为中国参赛人数最多、影响最大的计算机竞赛。在权威的全国普通高校学科竞赛排行榜上，蓝桥杯大赛名列其中，是广受欢迎的信息类专业竞赛。蓝桥杯大赛的奖牌是大学生计算机能力的有力证明。  本书读者对象 这是一本“算法入门”书，写给“正在学或刚学过编程语言，但是数据结构、算法零基础”的初学者。 本书的读者符合这样的画像： 刚学过编程语言，C/C 、Java、Python这几种语言中的任何一个都可以； 有基本的编码能力，语法比较熟悉； 编过一些代码，但仍然不熟练； 不懂数据结构和算法，遇到较难的问题没有思路。 这位勤奋的读者有以下目标： （1） 数据结构和算法入门，建立计算思维。 （2） 大量编码，提高编码能力。 （3） 参加蓝桥杯大赛并获奖。 如果读者准备参加蓝桥杯全国软件和信息技术专业人才大赛（软件类），看这本书正合适，因为题目大多是蓝桥杯大赛的真题，并且按照蓝桥杯大赛的要求进行了详细的解析。 本书也适用于准备其他算法竞赛，例如全国青少年信息学奥林匹克竞赛（NOI）、国际大学生程序设计竞赛（ICPC）、中国大学生程序设计竞赛（CCPC）、中国高校计算机大赛团体程序设计天梯赛等，因为所有的算法竞赛的考点都是相通的。 用一句话概括本书的作用： 通过本书的学习，读者可以从一名蓝桥杯、算法竞赛的小白，成长为掌握算法知识、建立算法思维、具备编码能力的专业的计算机编程人才。  本书内容介绍 蓝桥杯大赛软件赛是蓝桥杯大赛中参赛人数最多的项目，包括Java软件开发、C/C 程序设计、Python程序设计三个子项。蓝桥杯大赛软件赛是算法竞赛，考核数据结构和算法，包括数据结构、基本算法、搜索、动态规划、数学、图论、字符串等。掌握这些知识点是计算机专业人才的核心能力。 蓝桥杯大赛官方在2023年发布《蓝桥杯大赛软件赛知识点大纲》，按难度分为三部分： 大学C组、大学B组、研究生及大学A组。本书内容精选了其中初级（≥大学C组）和部分中级（≥大学B组）知识，都是必考或常考知识点。还有一些中级和高级知识点，因为难度较高，不适合在入门阶段学习，本书没有涉及。下表是蓝桥杯大纲与本书内容的对照。 本书内容与蓝桥杯大纲知识点对照 组别蓝桥杯大赛软件赛知识点大纲本书对应章节 大学 C组 枚举第2章 杂题和填空题 排序： 冒泡排序、选择排序、插入排序4.1 十大排序算法 搜索： BFS、DFS 6.1 DFS代码框架 6.2 DFS常见应用 6.5 BFS基本代码 6.6 BFS与最短路径 6.7 BFS判重 模拟 前缀和 二分 贪心 5.2 前缀和 5.3 差分 5.4 二分 5.5 贪心 DP： 普通一维问题 8.1 动态规划的概念 8.2 动态规划的两种编码方法 8.3 DP设计基础 高精度 3.1 数组与高精度（C 版） 数据结构： 栈、队列、链表、二叉树第3章 数据结构基础 数学： 素数、GCD、LCM、快速幂 7.1 模运算 7.2 快速幂 7.3 素数 7.4 GCD和LCM 大学 B组 排序： 归并排序、快速排序、桶排序、堆排序、基数排序 4.1 十大排序算法 搜索： 剪枝 6.3 DFS剪枝 搜索： 双向BFS、记忆化搜索、迭代加深搜索、启发式搜索 （本书没有涉及） DP： 背包DP 8.4 DP背包 DP： 树形DP、状压DP、数位DP、DP的常见优化 （本书没有涉及） 字符串： 哈希、kmp、manacher （本书没有涉及） 图论： 最小生成树、单源最短路 9.2 最短路径算法 9.3 最小生成树 图论： 欧拉回路、差分约束系统、拓扑排序、二分图匹配、图的连通性问题（割点、桥、强连通分量）、DFS序、最近共同祖先 （本书没有涉及） 数学： 排列组合 4.2 排序函数 4.3 排列和组合 数学： 二项式定理、容斥原理、模意义下的逆元、矩阵运算、高斯消元 （本书没有涉及） 数据结构： 并查集 3.8 并查集 数据结构： ST表、堆、树状数组、线段树、Trie树 （本书没有涉及） 计算几何（基础计算和基本位置关系判定）； 概率论、博弈论 （本书没有涉及） 研究 生及 大学 A组 字符串（AC自动机、拓展kmp、后缀数组、后缀自动机、回文自动机）； 图论（网络流、一般图匹配）； 数学（生成函数、莫比乌斯反演、快速傅里叶变换）； 数据结构（树链剖分、二维/动态开点线段树、平衡树、可持久化数据结构、树套树、动态树） （本书没有涉及） 由于蓝桥杯软件赛有三种语言，所以作者编写了三个版本： 《蓝桥杯算法入门（C/C ）》、《蓝桥杯算法入门（Java）》和《蓝桥杯算法入门（Python）》，形成一个系列。这三个版本对数据结构和算法的理论讲解相同，选用的例题大部分一样。不同的内容也很多，例如C/C 的STL、Java的类、Python的字符和日期库，例题用各自的语言给出模板代码。 目前出版的算法竞赛书籍中，代码绝大部分都是用C/C 语言写的，极少有其他语言的版本。因此，本系列中的Java和Python版本填补了这一空白。 本书是C/C 版。C/C 组是参赛人数最多的组，占总人数的三分之二。C/C 有丰富的STL，本书在多个章节中详解了它的应用。例如“3.2 STL概述”详解了常用的功能，如String库、迭代器、容器、vector、常用函数、set、map，“3.3 链表、3.4队列、3.5优先队列、3.6栈”介绍了STL的数据结构，“4.2 排序函数”介绍了STL的sort()函数，“4.3 排列和组合”介绍了STL的next_permutation()。熟练掌握STL是竞赛队员的技能，能极大减小编码难度，缩短编码时间。  备赛经验 由于蓝桥杯的影响力，很多大学生在大一就会参加蓝桥杯软件赛，但是第一次参赛的新手往往铩羽而归。因为蓝桥杯大赛是极为专业、全面考核计算机能力的计算机竞赛，它对编码能力、算法知识、计算思维、计算机建模的要求极高。 刚接触蓝桥杯大赛的学生往往有这样的困惑： 蓝桥杯大赛似乎很难、很花时间，不仅难以入门，而且学习成本很高，至少需要高强度学习半年以上才有可能得奖，然后再用一年甚至两年的勤奋学习，才能取得好成绩。每个读者都希望有一个性价比很高的学习方法： 学习时间尽量少，得奖尽量大！那么，阅读这本书是得奖的捷径吗？答案是薛定谔之猫： 是，也不是。 回答“是”。这本书指引了一条合适的、正确的蓝桥杯备赛之路，让读者少走弯路。本书包括了蓝桥杯省赛二等奖所需的知识点，讲解了大量的大赛真题，并列出了巩固知识点所需要的练习题。本书的章节是按照学习难度循序渐进地展开的，读者只需要按从前到后的顺序阅读即可。只要用心看书并大量做题，得奖有相当的保证。 回答“不是”。“捷径”往往是“艰难”的代名词，“捷径”往往更费力，正如爬山的捷径更陡峭、更费力一样。读者是否能走通这个捷径，取决于你花费的精力有多少。简单地说，算法竞赛没有轻松的学习方法，一切都是“硬”实力，没有花哨的投机取巧。 还有一点让低年级参赛者感到压力巨大： 竞赛涉及的知识点是“超纲”的，往往在大三、大四的专业课程中才会涉及，甚至很多知识点根本就不会在计算机专业的课程中出现，这些知识点中有一些是很基本的考点； 而且蓝桥杯软件赛不是那种短期培训就能迅速获得成绩的竞赛，如果等到大三或大四才参赛，已经来不及了。如何解决“超纲”问题？这就是本书的意义： 算法竞赛需要拓展大量课外的专业知识，很多拓展内容在本书中进行了详细介绍。当然，本书定位是“入门”，只拓展了部分知识，更全面的算法知识点解析请阅读作者的另一本书《算法竞赛》，这是一本算法大全，覆盖了95%的算法竞赛知识点。 在准备蓝桥杯大赛时，请注意以下几个重要问题。 （1） 刷题。 备赛需要大量做题，这是最重要的一条。只读理论、只看书，而不做题，学习效果只会略大于零，对知识点的理解无法转化为能编码解决问题的“硬实力”。刷多少题合适？本书介绍了算法竞赛中的常见初级和中级知识点，每个知识点做10~20题，总共做600题左右，这是蓝桥杯算法入门需要的最少做题量。 （2） 速度。 参加蓝桥杯大赛，编码速度极为重要。比赛时间只有4小时，非常紧张。编码速度决定了获奖的级别。如何提高编码速度？有以下技巧。  熟练掌握集成编译环境。把编译环境变成得心应手的工具。  快速读题。每道题需要建模后才能编码。快速读完题目并想出合适的算法，这需要经过大量的做题训练。训练的时候提高大脑的兴奋度，用最快的速度理解题目并建立计算机编码模型。  减少调试。写好程序后，争取能一次通过测试样例。为了减少调试，尽量使用不容易出错的方法，例如少用指针、多用静态数组、把逻辑功能模块化等，不要使用动态调试方法，不要使用单步跟踪、断点等调试工具。如果需要查看中间的运行结果，就在代码中的关键地方打印出调试信息。  使用库函数。如果题目涉及比较复杂的数据处理，用库函数可以大大减少编码量，而且能减少错误的发生。平时注意积累C/C 、Java、Python语言的库函数，并做到熟练应用。 （3）模板。 模板是某些数据结构、算法的标准代码。模板代码是计算机科学发展过程中凝练出的精华。 模板很有用，例如并查集模板、快速幂模板、埃氏筛模板等，需要牢记并熟练应用。学习经典算法时，需要整理代码模板并多次学习和使用它。 有的算法竞赛可以带纸质资料进场，相当于开卷考试，例如ICPC、CCPC，很多竞赛队员带了厚厚的打印代码和各种书籍进场参赛。但是蓝桥杯大赛禁止带任何资料进场，是闭卷考试，完全靠脑力，需要记住模板。这增加了一些难度。 有初学者问： 我想速成，来不及做很多题，不过我可以多准备一些模板，把模板背会，是不是也能获奖？回答是： 模板有用且需要掌握，但赛场上模板的用处有限。不同的编程题目，即使用到相同的算法或数据结构，也往往不能用同样的代码，而需要做很多修改，因为不同环境下的变量和数据规模是不同的。对模板的学习和使用，需要多花一些时间，融会贯通，不能急躁。注意，模板的代码需要自己真正理解、熟练掌握并多次使用过，才能在做题的时候快速应用到编码中。 最后用一段话寄语读者。教育的目的是什么？英国教育家怀特海说： “学生是有血有肉的人，教育的目的是激发和引导他们的自我发展之路。”算法竞赛就是促进学生自我发展的一条康庄大道。大学的创新学习有三条途径，缺一不可： 一是以竞促学； 二是以研促学； 三是以创促学。参加算法竞赛，好处体现在很多方面： 保研、奖学金、考研、就业、出国、创新学分。本书将帮助你掌握算法竞赛知识，建立计算思维，提高编程能力，在算法竞赛中披荆斩棘，立于不败之地。 罗勇军杨建国 2024年8月于上海 第5章〓基本算法 基本算法没有复杂的逻辑和步骤，但是计算效率高、应用场景丰富，是算法竞赛必考的知识点。 在算法竞赛中有一些“通用”的算法，例如尺取法、二分法、倍增法、前缀和、差分、离散化、分治、贪心等。这些算法没有复杂的逻辑，代码也简短，但是它们的应用场合多，效率也高，广泛应用在编程和竞赛中。在蓝桥杯大赛中，这些算法几乎是必考的。本章介绍前缀和、差分、二分、贪心。 5.1算法与算法复杂度 在前面几章讲解例题时有很多题分析了“算法复杂度”，使读者对算法分析有了一定的了解。算法分析是做竞赛题时的一个必要步骤，用于评估问题的难度和决定使用什么算法来求解。在蓝桥杯这种赛制中，一道题往往可以用多种算法求解，例如较差的算法可以通过30%的测试，中等的算法可以通过70%的测试，优秀的算法可以通过100%的测试。 5.1.1算法的概念 “程序=算法 数据结构”。算法是解决问题的逻辑、方法、过程，数据结构是数据在计算机中的存储和访问方式，两者紧密结合解决复杂问题。 算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。它有以下5个特征: （1） 输入。一个算法有零个或多个输入。程序可以没有输入，例如一个定时闹钟程序，它不需要输入，但是能够每隔一段时间就输出一个报警。 （2） 输出。一个算法有一个或多个输出。程序可以没有输入，但是一定要有输出。 （3） 有穷性。一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成。 （4） 确定性。算法中的每一条指令必须有确切的含义，对于相同的输入，只能得到相同的输出。 （5） 可行性。算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 5.1.2计算资源 计算机软件运行需要的资源有两种: 计算时间和存储空间。资源是有限的，一个算法对这两种资源的使用程度可以用来衡量该算法的优劣。 时间复杂度: 代码运行需要的时间。 空间复杂度: 代码运行需要的存储空间。 与这两个复杂度对应，程序设计题会给出对运行时间和空间的说明，例如“时间限制: 1s，内存限制: 256MB”，参赛队员提交到判题系统的代码需要在1s内运行结束，且使用的空间不能超过256MB，若有一个条件不满足就判错。 这两个限制条件非常重要，是检验代码性能的参数，所以队员拿到题目后第一步需要分析代码运行需要的计算时间和存储空间。 如何衡量代码运行的时间？通过代码打印运行时间，可以得到一个直观的认识。 下面的C 代码只有一个while循环语句，代码对k累加n次，最后打印运行时间。用clock()函数统计时间。 1#include 2using namespace std; 3int main(){ 4 int k = 0， n = 1e8;//一亿 5 clock_t s = clock();//开始时间 6 while(n--) k = 5;//循环n次 7 clock_t t = clock();//终止时间 8 cout << (double)(t - s) / CLOCKS_PER_SEC;//打印运行时间 9} 在作者的笔记本或计算机上运行，循环n=1亿次，输出的运行时间是0.158s; 换了一台台式计算机，运行时间是0.057s。 竞赛评测用的判题服务器（OJ系统），性能可能比这个好一些，也可能差不多。对于C 题目，如果题目要求“时间限制: 1s”，那么内部的循环次数n应该在一亿次以内，Java也在一亿次以内。对于同等规模的Python题目，时间限制一般是5~10s。 由于代码的运行时间依赖于计算机的性能，不同的机器结果不同，所以直接把运行时间作为判断标准并不准确。用代码执行的“计算次数”来衡量更加合理，例如上述代码循环了n次，把它的运行次数记为O(n)，这称为计算复杂度的“大O记号”。 5.1.3算法复杂度 衡量算法性能的主要标准是时间复杂度。 时间复杂度比空间复杂度更重要。一个算法使用的空间很容易分析，而时间复杂度往往关系到算法的根本逻辑，更能说明一个程序的优劣。因此，如果不特别说明，在提到“复杂度”时一般指时间复杂度。 竞赛题一般情况下做简单的时间复杂度分析即可，不用精确计算，常用“大O记号”做估计。 例如，在一个有n个数的无序数列中查找某个数x，可能第一个数就是x，也可能最后一个数才是x，平均查找时间是n/2次，最差情况需要查找n次; 把查找的时间复杂度记为最差情况下的O(n)，而不是O(n/2)。按最差情况算，是因为判题系统可能故意用“很差”的数据来测试。再例如，冒泡排序算法的计算次数约等于n2/2次，但是仍记为O(n2)，而不是O(n2/2)，这里把常数 1/2系数忽略了。 另外，即使是同样的算法，不同的人写出的代码的效率也不一样。OJ系统所判定的运行时间是整个代码运行所花的时间，而不是理论上算法所需要的时间。同一个算法，不同的人写出的程序，复杂度和运行时间可能差别很大，跟他使用的编程语言、逻辑结构、库函数等都有关系。所以竞赛队员需要进行训练，提高自己的编码能力，纠正自己不合理的写代码的习惯。 用“大O记号”表示的算法复杂度有以下分类。 （1） O(1)，常数时间。计算时间是一个常数，和问题的规模n无关。例如，在用公式计算时，一次计算的复杂度就是O(1); 哈希算法，用hash函数在常数时间内计算出存储位置; 在矩阵A［M］［N］中查找i行j列的元素，只需要访问一次A［i］［j］就够了。 （2） O(log2n)，对数时间。计算时间是对数，通常是以2为底的对数，在每一步计算后，问题的规模减小一半。例如在一个长度为n的有序数列中查找某个数，用折半查找的方法只需要log2n次就能找到。O(log2n)和O(1)没有太大的差别。例如n=1000万时，log2n<24。 （3） O(n)，线性时间。计算时间随规模n线性增长。在很多情况下，这是算法可能达到的最优复杂度，因为对输入的n个数，程序一般需要处理所有的数，即计算n次。例如查找一个无序数列中的某个数，可能需要检查所有的数。再例如图问题，有V个点和E条边，大多数图问题都需要搜索所有的点和边，复杂度的最优上限是O(V E)。 （4） O(nlog2n)。这常是算法能达到的最优复杂度。例如分治法，一共O(log2n)个步骤，每个步骤对每个数操作一次，所以总复杂度是O(nlog2n)。例如n=100万时，nlog2n=2000万。 （5） O(n2)。一个两重循环的算法，复杂度是O(n2)。类似的复杂度有O(n3)、O(n4)等。 （6） O(2n)。一般对应集合问题，例如一个集合中有n个数，这些数不分先后，子集共有2n个。 （7） O(n!)。一般对应排列问题。如果集合中的数分先后，按顺序输出所有的排列，共有O(n!)个。 把上面的复杂度分成两类: （1）多项式复杂度，包括O(1)、O(n)、O(nlog2n)、O(nk)等，其中k是一个常数; （2）指数复杂度，包括O(2n)、O(n!)等。 如果一个算法是多项式复杂度，称它为“高效”算法； 如果是指数复杂度，则是一个“低效”算法。 竞赛题目的限制时间，C/C 一般给1s，Java一般给3s，Python一般给5~10s。对应普通计算机的计算速度是每秒几千万次计算。那么上述的时间复杂度可以换算出能解决问题的数据规模。例如，如果一个算法的复杂度是O(n!)，当n=11时，11!=39916800，这个算法只能解决n≤11的问题。问题规模和可用算法如表5.1所示。 表5.1问题规模和可用算法 问题规模n 可用算法的时间复杂度 O(log2n) O(n) O(nlog2n) O(n2) O(2n) O(n!) n≤11 √ √ √ √ √ √ n≤25 √ √ √ √ √ × n≤5000 √ √ √ √ × × n≤106 √ √ √ × × × n≤107 √ √ × × × × n>108 √ × × × × × 大家在拿到题目后，一定要分析自己准备使用的算法的复杂度，评估自己的代码能通过多少测试。 5.2前缀和 5.2.1前缀和的概念 前缀和是一种操作简单但是非常有效的优化方法，能把计算复杂度为O(n)的区间计算优化为O(1)的端点计算。 前缀和是出题者喜欢考核的知识点，在算法竞赛中很常见，在蓝桥杯大赛中几乎必考，原因有以下两点: （1） 原理简单，方便在很多场合下应用，与其他考点结合。 （2） 可以考核不同层次的能力。前缀和的题目一般也能用暴力法求解，暴力法能通过30%的测试，用前缀和优化后能通过70%~100%的测试。 首先了解“前缀和”的概念。一个长度为n的数组a［1］~a［n］，前缀和sum［i］等于a［1］~a［i］的和: sum［i］=a［1］ a［2］ … a［i］ 使用递推，可以在O(n)时间内求得所有前缀和: sum［i］=sum［i-1］ a［i］ 如果预计算出前缀和，就能使用它快速计算出数组中任意一个区间a［i］~a［j］的和。即: a［i］ a［i 1］ … a［j-1］ a［j］=sum［j］-sum［i-1］ 上式说明，复杂度为O(n)的区间求和计算优化为了O(1)的前缀和计算。 5.2.2例题 前缀和是一种很简单的优化技巧，应用场合很多，在竞赛中极为常见。如果大家对题目建模时发现有区间求和的操作，可以考虑使用前缀和优化。 第1章曾用例题“求和”介绍了前缀和的应用，下面再举几个例子。 例5.1可获得的最小取值lanqiaoOJ 3142 问题描述: 有一个长度为n的数组a，进行k次操作来取出数组中的元素。每次操作必须选择以下两种操作之一: （1）取出数组中的最大元素; （2）取出数组中的最小元素和次小元素。要求在进行完k次操作后取出的数的和最小。 输入: 第一行输入两个整数n和k，表示数组长度和操作次数。第二行输入n个整数，表示数组a。 数据范围: 3≤n≤2×105，1≤ai≤109，1≤k≤99999，2k 2using namespace std; 3const int N = 200010; 4long long a［N］，sum［N］;//sum［］是a［］的前缀和 5int main(){ 6 int n， k; 7 cin >> n >> k; 8 for(int i = 1; i <=n; i ) scanf(”%lld”，&a［i］); 9 sort(a 1， a 1 n); 10 for(int i = 1; i <=n; i ) sum［i］ = sum［i-1］ a［i］; 11 long long ans = 1e18; 12 for(int p = 1; p <=k; p ) 13ans = min(sum［n］ - sum［n p-k］ sum［2*p］， ans); 14 cout << ans; 15 return 0; 16} 再看一道简单题。 例5.2并行处理http://oj.ecustacm.cn/problem.php?id=1811 问题描述: 现在有n个任务需要到GPU上运行，但是只有两块GPU，每块GPU一次只能运行一个任务，两块GPU可以并行处理。给定n个任务需要的时间，需要选择一个数字i，将任务1到任务i放到第一块GPU上运行，将任务i 1到任务n放到第二块GPU上运行。请求出最短运行时间。 输入: 输入的第一行为正整数n，1≤n≤100000。第二行为n个整数ai，表示第i个任务需要的时间，1≤ai≤109。 输出: 输出一个数字，表示答案。 输入样例: 3 4 2 3 输出样例: 5 题目的意思是把n个数划分为左右两部分，分别求和，其中一个较大、一个较小，问在所有可能的划分情况中较大的和最小是多少？因为n比较大，需要一个约为O(n)的算法。 这是一道很直接的前缀和题目。用前缀和在O(n)的时间内预计算出所有的前缀和sum［］。若在第i个位置划分，左部分的和是sum［i］，右部分的和是sum［n］-sum［i］。在所有的划分中，较大的和的最小值是min(ans，max(sum［i］，sum［n］-sum［i］))。 下面是代码。 1#include 2using namespace std; 3const int N = 1e5 10; 4long long sum［N］;//前缀和 5int main(){ 6 int n; cin >> n; 7 for(int i = 1; i <=n; i ) { 8int a; cin >> a; 9sum［i］ = sum［i-1］ a;//求前缀和 10 } 11 long long ans = sum［n］; 12 for(int i = 1; i <=n; i )//较大的和最小是多少 13ans = min(ans， max(sum［i］， sum［n］-sum［i］)); 14 cout << ans << endl; 15 return 0; 16} 下面的例题是前缀和在异或计算中的应用，也是常见的应用场景。 例5.32023年第十四届蓝桥杯省赛C/C 大学A组试题H: 异或和 之和lanqiaoOJ 3507 时间限制: 1s内存限制: 256MB本题总分: 20分 问题描述: 给定一个数组ai，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足1≤L≤R≤n的L、R，求出数组中第L至第R个元素的异或和。然后输出每组L、R得到的结果加起来的值。 输入: 输入的第一行包含一个整数n。第二行包含n个整数ai，相邻整数之间使用一个空格分隔。 输出: 输出一个整数，表示答案。 输入样例: 5 1 2 3 4 5 输出样例: 39 评测用例规模与约定： 对于30%的评测用例，n≤300; 对于60%的评测用例，n≤5000; 对于所有评测用例，1≤n≤105，0≤ai≤220。 n个a1~an的异或和是指a1a2…an。 下面给出3种方法，分别通过30%、60%、100%的测试。 （1） 通过30%的测试。 本题的简单做法是直接按题意计算所有子段的异或和，然后加起来。 有多少个子段？ 长度为1的子段异或和有n个: a1，a2，…，an 长度为2的子段异或和有n-1个: a1a2，a2a3，…，an-1an …… 长度为n的子段异或和有一个: a1a2a3…an-1an 共n2/2个子段。 下面代码中第8、9行遍历所有的子段［L，R］，第11行求［L，R］的子段和，共3重for循环，计算复杂度为O(n3)，只能通过30%的测试。 1#include 2using namespace std; 3int main(){ 4 int n; cin >> n; 5 vector a(n);//用vector定义数组a［］ 6 for(int i = 0; i < n; i ) cin >> a［i］; 7 long long ans=0;//注意这里用long long 8 for(int L=0;L 2using namespace std; 3int main(){ 4 int n; cin >> n; 5 vector a(n); 6 for(int i = 0; i < n; i ) cin >> a［i］; 7 long long ans = 0; 8 for(int L = 0; L < n; L ) { 9long sum = 0;//sum是包含a［L］的子段的前缀和 10for(int R = L; R < n; R ) { 11sum ^= a［R］;//用递推求前缀和sum 12ans = sum;//累加所有子段和 13} 14 } 15 cout << ans << endl; 16 return 0; 17} （3） 通过100%的测试。 本题有没有进一步的优化方法？这就需要仔细分析异或的性质了。根据异或的定义，有aa=0、0a=a、00=0。推导子段ai~aj的异或和: aiai 1…aj-1aj=(a1a2…ai-1)(a1a2…aj) 记si=a1a2…ai，这是异或形式的前缀和。上式转化为: aiai 1…aj-1aj=si-1sj 若si-1=sj，则si-1sj=0; 若si-1≠sj，则si-1sj=1。题目要求所有子段异或和相加的结果，这等于判断所有的{si，sj}组合，若si≠sj，则结果加1。 如何判断两个s是否相等？可以用位操作的技巧，如果它们的第k位不同，则两个s肯定不等。下面以a1=011，a2=010为例，分别计算第k位的异或和，并且相加: k=0，第0位异或和，s1=1，s2=10=1，ans0=a1 a2 a1a2=s1 s1s2 s2=1 0 1=2 k=1，第1位异或和，s1=1，s2=11=0，ans1=a1 a2 a1a2=s1 s1s2 s2=1 1 0=2 k=2，第2位异或和，s1=0，s2=00=0，ans2=a1 a2 a1a2=s1 s1s2 s2=0 0 0=0 最后计算答案: ans=ans0×20 ans1×21 ans2×22=6。 本题0≤ai≤220，所有的前缀和s都不超过20位。代码中第8行逐个计算20位的每一位，第11行的for循环计算n个前缀和，总计算量约为20×n。 1#include 2using namespace std; 3int main() { 4 int n; cin >> n; 5 vector a(n); 6 for(int i = 0; i < n; i ) cin >> a［i］; 7 long long ans = 0; 8 for(int k=0;k<=20;k ){//所有a不超过20位 9int zero=1，one=0;//统计第k位的0和1的数量 10long long cnt=0，sum=0;//cnt用于统计第k位有多少对si⊕sj =1 11for(int i=0;i>k)&1;//取a［i］的第k位 13sum ^= v; 14//对所有a［i］的第k位做异或得到sum，sum等于0或1 15if(sum==0){//前缀和为0 16zero ;//0的数量加1 17cnt =one; 18//这次sum=0，这个sum跟前面等于1的sum异或得1 19}else{//前缀异或为1 20one ;//1的数量加1 21cnt =zero; 22//这次sum=1，这个sum跟前面等于0的sum异或得1 23} 24} 25ans = cnt*(1ll< 2using namespace std; 3const int N=1005; 4int a［N］［N］，s［N］［N］; 5int main() { 6 int n，m，c; cin>>n>>m>>c; 7 for(int i=1;i<=n;i ) 8for(int j=1;j<=m;j ){ 9cin >> a［i］［j］; 10s［i］［j］ = s［i-1］［j］ s［i］［j-1］-s［i-1］［j-1］ a［i］［j］; 11} 12 int Max = -1<<30， x， y; 13 for(int x1=1;x1<=n-c 1;x1 ) 14for(int y1=1;y1<=m-c 1;y1 ){//枚举所有坐标点 15int x2=x1 c-1，y2=y1 c-1; //正方形的右下角坐标 16int ans = s［x2］［y2］-s［x2］［y1-1］-s［x1-1］［y2］ s［x1-1］［y1-1］; 17if(ans > Max){ 18Max = ans; 19x=x1， y=y1; 20} 21} 22 cout< 2using namespace std; 3const int N=1e5 3; 4int a［N］，cnt［N］;//a［］:读入数组；cnt［i］：第i个数被加的次数 5int main(){ 6 int n; scanf(”%d”， &n); 7 for(int i=1;i<=n;i ) scanf(”%d”， &a［i］); 8 int m; scanf(”%d”， &m); 9 long long ans1=0，ans2=0; //ans1: 原区间和； ans2: 新区间和 10 while(m--){ 11int L，R; scanf(”%d%d”， &L， &R); 12for(int i=L;i<=R;i ) 13cnt［i］ ;//第i个数被加了一次，累计一共加了多少次 14 } 15 for(int i=1; i<=n; i ) 16ans1 = (long long)a［i］*cnt［i］;//在原数组上求区间和 17 sort(a 1，a 1 n); 18 sort(cnt 1，cnt 1 n); 19 for(int i=1;i<=n;i ) 20ans2 = (long long)a［i］*cnt［i］; 21 printf(”%lld＼n”， ans2-ans1);//注意，%lld不要写成 %d 22 return 0; 23} （2） 通过100%的测试。 本题是差分优化的直接应用。 前面提到，70%的代码效率低的原因是用第12行的for循环计算cnt［］。根据差分的应用场景，每次查询的［L，R］就是对a［L］~a［R］中的所有数累加的次数加1，也就是对cnt［L］~cnt［R］中的所有cnt［］加1。那么对cnt［］使用差分数组d［］即可。 下面代码的第13行用差分数组d［］记录cnt［］的变化，第17行用d［］恢复得到cnt［］。其他部分和前面的70%代码一样。 对于代码的计算复杂度，第11行的while只有O(m)，最耗时的是第20、21行的排序，复杂度为O(nlog2n)，能通过100%的测试。 1#include 2using namespace std; 3const int N = 1e5 3; 4int a［N］，d［N］，cnt［N］; 5int main() { 6 int n; scanf(”%d”， &n); 7 for(int i=1;i<=n;i ) 8scanf(”%d”， &a［i］); 9 int m; scanf(”%d”， &m); 10 long long ans1=0，ans2=0; 11 while(m--){ 12int L，R; scanf(”%d%d”， &L， &R); 13d［L］ ; d［R 1］--; 14 } 15 cnt［0］ = d［0］; 16 for(int i=1; i<=n; i ) 17cnt［i］ = cnt［i-1］ d［i］;//用差分数组d［］求cnt［］ 18 for(int i=1; i<=n; i ) 19ans1 = (long long)a［i］ * cnt［i］; 20 sort(a 1，a 1 n); 21 sort(cnt 1，cnt 1 n); 22 for(int i=1; i<=n; i ) 23ans2 = (long long)a［i］ * cnt［i］; 24 printf(”%lld＼n”， ans2-ans1); 25 return 0; 26} 再看一道例题。 例5.6推箱子http://oj.ecustacm.cn/problem.php?id=1819 问题描述: 在一个高度为H的箱子的前方有一个长和高均为N的障碍物。障碍物的每一列存在一个连续的缺口，第i列的缺口从第l个单位到第h个单位（从底部由0开始数）。现在需要清理出一条高度为H的通道，使得箱子可以直接推出去。请输出最少需要清理的障碍物面积。图5.4为样例中的障碍物，长和高均为5，箱子的高度为2，不需要考虑箱子会掉入某些坑中，最少需要移除两个单位的障碍物可以造出一条高度为2的通道。 图5.4推箱子样例 输入: 输入的第一行为两个正整数N和H，表示障碍物的尺寸和箱子的高度，1≤H≤N≤1000000。接下来N行，每行包含两个整数li和hi，表示第i列缺口的范围，0≤li≤hi 2using namespace std; 3typedef long long ll; 4const int N = 1e6 10; 5ll d［N］， a［N］， sum［N］; 6int main(){ 7 int n， h; scanf(”%d%d”，&n，&h); 8 for(int i = 1; i <=n; i ) { 9int li， hi; 10scanf(”%d%d”，&li，&hi);//本题n≤1000000，scanf输入比cin快 11d［li］ ;//可替换为sum［li］ ; 12d［hi 1］--;//可替换为sum［hi 1］--; 13 } 14 //用差分数组计算原数组 15 for(int i = 1; i <=n; i ) 16a［i］ = a［i-1］ d［i-1］;//可替换为sum［i］ = sum［i-1］; 17 //用原数组计算前缀和数组 18 for(int i = 1; i <=n; i ) 19sum［i］ = sum［i-1］ a［i］;//可替换为sum［i］ = sum［i-1］; 20 ll ans = sum［h-1］; 21 for(int left = 1; left h-1 <= n; left ) 22ans = max(ans， sum［left h-1］ - sum［left-1］); 23 cout << (ll)n * h - ans << endl; 24 return 0; 25} 5.3.2二维差分 从一维差分容易扩展到二维差分。一维是线性数组，一个区间［L，R］有两个端点; 二维是矩阵，一个区间由4个端点围成。设矩阵是n行n列的。 对比一维差分和二维差分的效率: 一维差分的一次修改是O(1)的，二维差分的修改也是O(1)的，设有m次修改; 一维差分的一次查询是O(n)的，二维差分是O(n2)的，所以二维差分的总复杂度是O(m n2)。由于计算一次二维矩阵的值需要O(n2)次计算，所以二维差分已经达到了最好的复杂度。 下面从一维差分推广到二维差分。由于差分是前缀和的逆运算，首先需要从一维前缀和推广到二维前缀和，然后从一维差分推广到二维差分。 在一维差分中，数组a［］是从第1个D［1］开始的差分数组D［］的前缀和: a［k］=D［1］ D［2］ … D［k］ 在二维差分中，a［］［］是差分数组D［］［］的前缀和。在由原点坐标(1，1)和坐标(i，j)围成的矩阵中，所有的D［］［］相加等于a［i］［j］。 可以把每个D［］［］看成一个小格子; 在坐标(1，1)和(i，j)所围成的范围内，所有小格子加起来的总面积等于a［i］［j］。每个格子的面积是一个D［］［］，例如阴影格子是D［i］［j］，它由4个坐标点定义: (i-1，j)、(i，j)、(i-1，j-1)、(i，j-1)。坐标点(i，j)的值是a［i］［j］，它等于坐标(1，1)和(i，j)所围成的所有格子的总面积。图5.5演示了这些关系。 图5.5把每个a［］［］看成总面积，把每个D［］［］看成小格子的面积 在一维情况下，差分是D［i］=a［i］-a［i-1］。在二维情况下，差分变成了相邻的a［］［］的“面积差”，计算公式如下: D［i］［j］=a［i］［j］-a［i-1］［j］-a［i］［j-1］ a［i-1］［j-1］ 这个公式可以通过上面的图来观察。阴影方格表示D［i］［j］的值，它的面积这样求: 大面积a［i］［j］减去两个小面积a［i-1］［j］、a［i］［j-1］，由于两个小面积的公共面积a［i-1］［j-1］被减了两次，所以需要加一次回来。 差分最关键的操作是区间修改。在一维情况下，做区间修改只需要修改区间的两个端点的D［］值。在二维情况下，一个区间是一个小矩阵，有4个端点，需要修改这4个端点的D［］［］值。例如坐标点(x1，y1)~(x2，y2)定义的区间，对应4个端点的D［］［］: 1D［x1］［y1］ = d;//二维区间的起点 2D［x1］［y2 1］ -= d;//把x看成常数，y从y1到y2 1 3D［x2 1］［y1］ -= d;//把y看成常数，x从x1到x2 1 4D［x2 1］［y2 1］ = d;//由于前两式把d减了两次，多减了一次，这里加一次回来 图5.6演示了区间修改。两个黑色点围成的矩形是题目给出的区间修改范围，只需要改变4个D［］［］值，即改变图中4个阴影块的面积。 图5.6二维差分的区间修改 读者可以用这个图观察每个坐标点的a［］［］值的变化情况。例如符号“Δ”标记的坐标(x2 1，y2)，它在修改的区间之外; a［x2 1］［y2］的值是从(1，1)到(x2 1，y2)的总面积，在这个范围内，D［x1］［y1］ d，D［x2 1］［y1］-d，两个d抵消，a［x2 1］［y2］保持不变。 下面的例题是二维差分的直接应用。 例5.72023年第十四届蓝桥杯省赛Java大学A组试题D: 棋盘 lanqiaoOJ 3533 时间限制: 3s内存限制: 512MB本题总分: 10分 问题描述: 小蓝拥有n×n大小的棋盘，一开始棋盘上都是白子。小蓝进行了m次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。 输入: 输入的第一行包含两个整数n、m，用一个空格分隔，表示棋盘的大小与操作数。接下来m行，每行包含4个整数x1、y1、x2、y2，相邻整数之间使用一个空格分隔，表示将在x1至x2行和y1至y2列中的棋子的颜色取反。 输出: 输出n行，每行n个0或1，表示该位置上棋子的颜色。如果是白色，输出0，否则输出1。 输入样例: 3 3 1 1 2 2 2 2 3 3 1 1 3 3 输出样例: 001 010 100 评测用例规模与约定： 对于30%的评测用例，n，m≤500; 对于所有评测用例，1≤n，m≤2000，1≤x1≤x2≤n，1≤y1≤y2≤m。 下面用两种方法求解，分别通过30%和100%的测试。 （1） 模拟，通过30%的测试。 按题目的描述编码实现。第6、9、10行有三重for循环，计算复杂度为O(mn2)，只能通过30%的测试。 1#include 2using namespace std; 3int a［2100］［2100］; 4int main(){ 5 int n，m; cin>>n>>m; 6 for(int i=0;i>x1>>y1>>x2>>y2; 9for(int i=x1;i<=x2;i ) 10for(int j=y1;j<=y2;j ) 11a［i］［j］ ^=1; 12 } 13 for(int i=1;i<=n;i ){ 14for(int j=1;j<=n;j ) 15cout< 2using namespace std; 3const int N = 2200; 4int a［N］［N］，d［N］［N］; 5int n，m; 6void insert(int x1，int y1，int x2，int y2){ 7 d［x1］［y1］ ;//d［x1］［y1］^=1; 8 d［x1］［y2 1］--; //d［x1］［y2 1］ ^=1; 9 d［x2 1］［y1］--; //d［x2 1］［y1］ ^=1; 10 d［x2 1］［y2 1］ ; //d［x2 1］［y2 1］ ^=1; 11} 12int main(){ 13 cin >>n>>m; 14 while(m--){ 15int x1，y1，x2，y2; 16cin >> x1 >>y1>>x2>>y2; 17insert(x1，y1，x2，y2); 18 } 19 for(int i=1;i<=n;i ) { 20for(int j=1;j<=n;j ){ 21a［i］［j］ = d［i］［j］ a［i-1］［j］ a［i］［j-1］ - a［i-1］［j-1］; 22cout << (a［i］［j］&1); 23} 24cout< 2using namespace std; 3int a［105］; 4bool check(int x，int mid){//二分中的检查函数 5 return x <=a［mid］;//如果x小于或等于中间数，返回true 6} 7int bin_search(int n， int x){//在数组a中找数字x，返回位置 8 int L = 1， R = n;//初始范围［L，R］ 9 while(L < R) { 10int mid = (L R)/2; 11if(check(x，mid)) R = mid;//答案在左半部分:［L，mid］ 12else L = mid 1;//答案在右半部分:［mid 1，R］ 13 } 14return a［L］;//返回答案 15} 16int main(){ 17 int n = 100; 18 for(int i=1;i<=n;i ) a［i］=i;//赋值，数字1~100 19 int x = 68;//猜68这个数 20 cout<<”x=”<>1 mid = L (R-L)/2 5.4.1二分法的经典应用 二分法的经典应用场景是“最小值最大化（最小值尽量大）”和“最大值最小化（最大值尽量小）”。 1. 最小值最大化 以“牛棚问题”为例。有n个牛棚，分布在一条直线上，有k头牛，给每头牛安排一个牛棚住，k 2using namespace std; 3#define ll long long 4ll check(ll n) {//计算n!的末尾有多少个0 5 ll cnt = 0; 6 while (n)cnt = (n /= 5); 7 return cnt; 8} 9int main(){ 10 ll k; cin >> k; 11 for(ll n=5;;n =5){//n是5的倍数，它含有因子5 12ll cnt = check(n);//cnt是n!的尾零数量 13if(cnt==k){cout << n; break;} 14if(cnt>k){cout <<-1; break;} 15 } 16 return 0; 17} （2） 通过100%的测试。 大家容易想到可以用二分优化，也就是用二分来猜n。因为当n递增时，尾零的数量也是单调递增的，符合二分法的应用条件。 下面讨论代码的计算复杂度。第12行的二分是O(log2E)，这里E=1019。第4行做一次check()，复杂度差不多是O(1)。总计算量约为log2E=log21019<70次。 1#include 2using namespace std; 3#define ll long long 4ll check(ll n) {//计算n!的末尾有多少个0 5 ll cnt = 0; 6 while (n) cnt = (n /= 5); 7 return cnt; 8} 9int main() { 10 ll k; cin >> k; 11 ll L = 0， R = 1e19;//R的初值为一个极大的数 12 while (L < R) { 13ll mid = (L R) >> 1; 14if (check(mid) >= k) //mid!的尾零数量超过了k，说明mid大了 15R = mid; 16else L = mid 1;//mid小了 17 } 18 if (check(R) == k)cout << R; 19 else cout << -1; 20 return 0; 21} 例5.92022年第十三届蓝桥杯省赛C/C 大学A组试题F: 青蛙过河 lanqiaoOJ 2097 时间限制: 1s内存限制: 256MB本题总分: 15分 问题描述: 小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降1，当石头的高度下降到0时小青蛙不能再跳到这块石头上（某次跳跃后使石头的高度下降到0是允许的）。小青蛙一共需要去学校上x天课，所以它需要往返2x次。当小青蛙具有一个跳跃能力y时，它能跳不超过y的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完x次课。 输入: 输入的第一行包含两个整数n、x，分别表示河的宽度和小青蛙需要去学校的天数。注意2x才是实际过河的次数。第二行包含n-1个非负整数H1、H2、…、Hn-1，其中Hi>0 表示在河中与小青蛙的家相距i的地方有一块高度为Hi的石头，Hi=0表示这个位置没有石头。 输出: 输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。 输入样例: 5 1 1 0 1 0 输出样例: 4 评测用例规模与约定： 对于30%的评测用例，n≤100; 对于60%评测用例，n≤1000; 对于所有评测用例，1≤n≤105，1≤x≤109，1≤Hi≤104。 往返累计2x次相当于单向走2x次。跳跃能力越大，越能保证可以通过2x次。用二分法找到一个最小的满足条件的跳跃能力。设跳跃能力为mid，每次能跳多远就跳多远，用二分法检查mid是否合法。 1#include 2using namespace std; 3int n， x; 4int h［100005］; 5int sum［100005］; 6bool check(int mid) { 7 for (int i = 1; i < n - mid 1; i ) //每个区间的高度之和都要大于或等于2x 8if (sum［i mid-1］ - sum［i-1］ < 2*x) 9return false; 10 return true; 11} 12int main() { 13 cin >> n >> x; 14 sum［0］ = 0; 15 for(int i = 1; i < n; i ){ 16cin >> h［i］; 17sum［i］ = sum［i - 1］ h［i］;//跳跃区间的高度之和 18 } 19 int L = 1， R = n; 20 while(L < R) { 21int mid = (L R)/2; 22if(check(mid)) R = mid; 23else L = mid 1; 24 } 25 cout << L; 26 return 0; 27} 例5.102023年第十四届蓝桥杯省赛Python大学B组试题D: 管道 lanqiaoOJ 3544 时间限制: 10s内存限制: 512MB本题总分: 10分 问题描述: 有一根长度为len的横向管道，该管道按照单位长度分为len段。每一段的中央有一个可开关的阀门和一个检测水流的传感器。一开始管道是空的，位于Li的阀门会在Si时刻打开，并不断地让水流入管道。对于位于Li的阀门，它流入的水在Ti (Ti≥Si)时刻会使得从第Li－(Ti－Si)段到第Li＋(Ti－Si)段的传感器检测到水流。求管道中每一段中间的传感器都检测到有水流的最早时间。 输入: 输入的第一行包含两个整数n、len，用一个空格分隔，分别表示会打开的阀门数和管道长度。接下来n行，每行包含两个整数Li、Si，用一个空格分隔，表示位于第Li 段管道中央的阀门会在Si时刻打开。 输出: 输出一个整数，表示答案。 输入样例: 3 10 1 1 6 5 10 2 输出样例: 5 评测用例规模与约定： 对于30%的评测用例，n≤200，Si，len≤3000; 对于70%的评测用例，n≤5000，Si，len≤105; 对于100% 的评测用例，1≤n≤105，1≤Si，len≤109，1≤Li≤len，Li-1>1) L而不是mid=(R L)>>1，是因为R L可能溢出。R的最大值是2e9，L的最大值是1e9，R L超过了int的范围。为什么第30行定义R的初值为2e9？请读者思考。 1#include 2using namespace std; 3const int N = 1e5 10; 4const int LEN = 1e9; 5int n， len; 6int L［N］， S［N］; 7bool check(int t){//检查t时刻，管道内是否都有水 8 int cnt = 0; 9 int last_L = 2， last_R = 1; 10 for(int i = 0; i < n; i ) 11if(t >=S［i］){ 12cnt ;//特判t是否够大 13int left = L［i］ - (t - S［i］); 14int right = L［i］ (t - S［i］); 15if(left < last_L) 16last_L = left， last_R = max(last_R， right); 17else if(left <=last_R 1) 18last_R = max(last_R， right); 19} 20 if(cnt == 0) return false; 21 if(last_L <=1 && last_R >=len) 22return true; 23 else 24return false; 25} 26int main(){ 27 scanf(”%d%d”， &n， &len); 28 for(int i = 0; i < n; i ) 29scanf(”%d%d”， &L［i］， &S［i］); 30 int LL = 0， R = 2e9， ans = -1;//LL避免和L［］重名 31 while(LL <=R){//二分 32int mid = ((R - LL) >> 1) LL; //如果写成(L R)>>1，可能溢出 33if(check(mid)) ans = mid， R = mid - 1; 34else LL = mid 1; 35 } 36 printf(”%d＼n”， ans); 37 return 0; 38} 下面是一道思维有难度的二分法题目。 例5.112022年第十三届蓝桥杯省赛C/C 大学C组试题I: 技能升级 lanqiaoOJ 2129 时间限制: 1s内存限制: 256MB本题总分: 25分 问题描述: 小蓝最近正在玩一款RPG 游戏。他的角色一共有n个可以增加攻击力的技能。其中第i个技能首次升级可以提升Ai点攻击力，以后每次升级增加的点数都会减少Bi。在「Ai/Bi(向上取整) 次之后，再升级该技能将不会改变攻击力。现在小蓝总计可以升级m次技能，他可以任意选择升级的技能和次数。请计算小蓝最多可以提高多少点攻击力？ 输入: 输入的第一行包含两个整数n和m。以下n行，每行包含两个整数Ai和Bi。 输出: 输出一行，包含一个整数，表示答案。 输入样例: 3 6 10 5 9 2 8 1 输出样例: 47 评测用例规模与约定： 对于40% 的评测用例，1≤n，m≤1000; 对于60%的评测用例，1≤n≤104; 1≤m≤107; 对于所有评测用例，1≤n≤105，1≤m≤2×109，1≤Ai，Bi≤106。 下面讲解3种方法，它们分别能通过40%、60%、100%的测试。 （1） 暴力法。 先试一下暴力法，直接模拟题意，升级m次，每次升级时选用攻击力最高的技能，然后更新它的攻击力。 下面是C 代码。复杂度是多少？第13行升级m次，是O(m)的; 第16~21行找最大攻击力，是O(n)的。总复杂度为O(mn)，只能通过40%的测试。 1#include 2using namespace std; 3const int N = 1010; 4int a［N］， b［N］， c［N］; //存ai、bi，ci=ai/bi 5int main() { 6 int n， m; 7 cin >> n >> m; 8 for (int i = 0; i < n; i ) { 9cin >> a［i］ >> b［i］; 10c［i］ = ceil(a［i］ / b［i］);//向上取整 11 } 12 int ans = 0; 13 for (int i = 0; i < m; i ) {//一共升级m次 14int max_num = a［0］;//每次升级时使用最大的攻击力 15int index = 0;//找最大攻击力对应的序号 16for (int j = 1; j < n; j ) { 17if (a［j］ > max_num) { 18max_num = a［j］; 19index = j; 20} 21} 22a［index］ -= b［index］;//更新攻击力 23if (c［index］ > 0) ans = max_num;//累加攻击力 24c［index］ -= 1; 25 } 26 cout << ans << endl; 27 return 0; 28} （2） 暴力法 优先队列。 上面的代码可以稍做改进。在n个技能中选用最高攻击力，可以使用优先队列，一次操作的复杂度为O(log2n)。m次升级，总复杂度为O(mlog2n)，能通过60%的测试。 下面用C 的优先队列priority_queue实现。priority_queue默认是大根堆，用top()读取队列中的最大值。 1#include 2using namespace std; 3typedef pair PII; 4priority_queue q;//默认是大根堆 5PII p; 6int main() { 7 int n， m; cin >> n >> m; 8 for (int i = 0; i < n; i ) { 9int a， b; cin >> a >> b; 10q.push(make_pair(a， b)); 11 } 12 long long ans = 0; 13 while (m--) {//升级m次 14if (q.empty()) break; 15p = q.top(); 16q.pop();//每次升级时使用最大的攻击力，读队列最大值并删除 17ans = p.first;//累加攻击力 18p.first -= p.second;//更新攻击力 19if (p.first > 0) q.push(p);//重新放进队列 20 } 21 cout << ans; 22 return 0; 23} （3） 二分法。 本题的正解是二分法，能通过100%的测试。 本题m≤2×109，太大，若逐一升级m次必定会超时，但是又不能直接对m进行二分，因为需要知道每个技能升级多少次，而这与m无关。 思考升级技能的过程，是每次找攻击力最高的技能。对某个技能，最后一次升级的攻击力肯定比之前升级的攻击力小，也就是前面的升级都更大。可以设最后一次升级提升的攻击力是mid，对每个技能，若它最后一次能升级mid，那么它前面的升级都更大。所有这样最后能达到mid的技能，它们前面的升级都应该使用。用二分法找到这个mid，另外，升级技能减少的攻击力的过程是一个等差数列，用O(1)次计算即可知道每个技能升级了几次。知道了每个技能升级的次数，就可以计算一共提升了多少攻击力，这就是题目的答案。 下面给出代码。check(mid)函数找这个mid。第13行，若所有技能升级的总次数大于或等于m次，说明mid设小了，在第25行让L增大，即增加mid。第13行，若所有技能升级的总次数小于m次，说明mid设大了，在第26行让R减小，即减小mid。 分析代码的复杂度。第23~27行，二分O（log2A)次，这里A表示1≤Ai≤106; 每次check()是O(n)，二分的总复杂度是O(nlog2A)。第30行的for循环是O(n)的。代码的总复杂度是O(nlog2A) O(n)，能通过100%的测试。 1#include 2using namespace std; 3typedef long long ll; //注意，此时需要用long long 4const int N = 100100; 5int a［N］， b［N］;//存ai、bi 6int n，m; 7bool check(ll mid) {//最后一次技能升级，最多能不能到mid 8 ll cnt = 0; 9 for (int i = 0; i < n; i) { 10if (a［i］ < mid) 11continue;//第i个技能的初值还不够mid，不用这个技能 12cnt = (a［i］ - mid) / b［i］ 1; //第i个技能用掉的次数 13if (cnt >=m) //所有技能升级的总次数大于或等于m次，说明mid设小了 14return true; 15 } 16 return false;//所有技能升级的总次数小于m次，说明mid设大了 17} 18int main() { 19 cin >> n >> m; 20 for (int i = 0; i < n; i) 21cin >> a［i］ >>b［i］; 22 ll L = 1， R = 1000000; //二分枚举最后一次攻击力最高能加多少 23 while (L <=R) { 24ll mid = (L R) / 2; 25if (check(mid)) L = mid 1; //增加mid 26else R = mid - 1;//减小mid 27 } 28 ll attack = 0; 29 ll cnt = m; 30 for (int i = 0; i < n; i) { 31if (a［i］ < R) continue; 32ll t = (a［i］ - L) / b［i］ 1;//第i个技能升级的次数 33if (a［i］ - b［i］ * (t - 1) == R) 34t -= 1; //这个技能每次升级刚好等于R，其他技能更好 35attack = (a［i］ * 2 - (t - 1) * b［i］) * t / 2; 36cnt -= t; 37 } 38 cout << attack cnt * R << endl; 39 return 0; 40} 【练习题】 二分的题目非常多，每个OJ网站都能用“二分”搜出很多二分题目。 lanqiaoOJ: 分巧克力99、跳石头364、课凑成的最大花束数3344、最大通过数3346、蓝桥A梦做铜锣烧3151、肖恩的苹果林3683、求函数零点4496、妮妮的月饼工厂3990、解立方根1217、一元三次方程求解764、二分查找数组元素1389。 5.5贪心 贪心（Greedy）是容易理解的算法思想: 把整个问题分解成多个步骤，在每个步骤都选取当前步骤的最优方案，直到所有步骤结束; 在每一步都不考虑对后续步骤的影响，在后续步骤中也不能回头改变前面的选择作者拟过两句赠言: “贪心说，我从不后悔我走过的路”，“贪心说，其实我有一点后悔，但是我回不了头”。大多数读者会选前一句。。 贪心策略在人们的生活中经常用到。例如下象棋时，初级水平的棋手只会“走一步看一步”，这就是贪心法； 而水平高的棋手能“走一步看三步”，轻松击败初级棋手，可以看成是动态规划。 贪心这种“只顾当下，不管未来”的解题策略让人疑惑: 在完成所有局部最优操作后得到的解不一定是全局最优，那么应该如何判断能不能用贪心呢？ 有时很容易判断: 一步一步在局部选择最优，最后结束时能达到全局最优。例如吃自助餐，怎么吃才能“吃回票价”？它的数学模型是一类背包问题，称为“部分背包问题”: 有一个容量为c的背包，有m种物品，第i种物品wi千克，单价为vi，且每种物品是可以分割的，例如大米、面粉等，问如何选择物品使得装满背包时总价值最大。此时显然可以用贪心法，只要在当前物品中选最贵的放进背包即可: 先选最贵的物品A，A放完之后，再选剩下的最贵的物品B，……，直到背包放满。 有时看起来能用贪心，但实际上贪心的结果不是最优解。例如最少硬币支付问题: 有多种面值的硬币，数量不限，需要支付m元，问怎么支付才能使硬币数量最少？ 最少硬币支付问题任意面值的最少硬币支付问题，正解是动态规划。请参考《算法竞赛入门到进阶》，清华大学出版社，罗勇军著，“7.1.1 硬币问题”给出了各种硬币问题的动态规划解法。是否能用贪心求最优解和硬币的面值有关。 如果硬币的面值为1元、2元、5元，用贪心是对的。贪心策略是当前选择可用的最大面值的硬币。例如支付m=18元，第一步选面值最大的5元硬币，用掉3个硬币，还剩3元; 第二步选面值第二大的2元硬币，用掉一个硬币，还剩1元; 最后选面值最小的1元硬币，用掉一个; 共用5个硬币。在这个解决方案中，硬币数量的总数是最少的，贪心法的结果是全局最优的。 但是如果是其他面值的硬币，贪心法就不一定能得到全局最优解。例如，硬币的面值很奇怪，分别是1、2、4、5、6元。支付m=9元，如果用贪心法，每次选择当前最大面值的硬币，那么答案是6 2 1，需要3个硬币，而最优解是5 4，只需要两个硬币。 概括地说，判断一个题目是不是能用贪心需要满足以下特征: （1） 最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。 （2） 贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择来得到。也就是说，通过一步一步局部最优能最终得到全局最优。 最后讨论贪心法的效率，贪心法的计算量是多少？贪心法由于每一步都在局部做计算，且只选取当前最优的步骤做计算，不管其他可能的计算方案，所以计算量很小。在很多情况下，贪心法可以说是计算量最少的算法了。与此相对，暴力法一般是计算复杂度最差的，因为暴力法计算了全局所有可能的方案。 由于贪心的效率高，所以如果一个问题确定可用贪心法得到最优解，那么应该使用贪心。如果用其他算法，大概率会超时。 在算法竞赛中，贪心法几乎是必考点，有的题考验思维能力，有的题结合了贪心和其他算法。虽然贪心策略很容易理解，但贪心题可能很难。 贪心也是蓝桥杯大赛的常见题型。不论是省赛还是国赛，贪心出现的概率都非常大。 虽然贪心法不一定能得到最优解，但是它解题步骤简单、编程容易、计算量小，得到的解“虽然不是最好，但是还不错！”。像蓝桥杯这种赛制，一道题有多个测试点，用贪心也许能通过10%~30%的测试，若别无他法，可以一试。 5.5.1经典贪心问题 1. 部分背包问题 前文介绍了用贪心求解部分背包问题，下面是例题。 例5.12部分背包问题https://www.luogu.com.cn/problem/P2240 问题描述: 有n(n≤100)堆金币，第i堆金币的总重量和总价值分别是mi、vi(1≤mi，vi≤100)。有一个承重量为c(c≤1000) 的背包，要求装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币的重量价值比（也就是单位价格）不变。请问最多可以拿走多少价值的金币？ 输入: 第一行两个整数n、c。接下来n行，每行两个整数mi、vi。 输出: 输出一个实数，表示答案，保留两位小数。 输入样例: 4 50 10 60 20 100 30 120 15 45 输出样例: 240.00 按单位价格排序，最贵的先拿，便宜的后拿。 1#include 2using namespace std; 3struct gold{double w，v，p;}a［105］;//w、v、p: 重量、价值、单价 4bool cmp(gold a， gold b){return a.p > b.p;} //单价从大到小排序 5int main(){ 6 int n，c; cin>>n>>c; 7 for(int i=0;i> a［i］.w >> a［i］.v; 9a［i］.p = a［i］.v/a［i］.w;//计算单价 10 } 11 sort(a，a n，cmp);//按单价排序 12 double sum=0.0;//最大价值 13 for(int i=0;i=a［i］.w){//第i种金币比背包容量小 15c -= a［i］.w;//背包还有余量 16sum = a［i］.v; //累计价值 17} 18else{//第i种金币很多，直接放满背包 19sum = c*a［i］.p; 20break; 21} 22 } 23 printf(”%.2f”，sum); //保留小数点后两位输出 24 return 0; 25} 2. 不相交区间问题 不相交区间问题或者称为区间调度问题、活动安排问题。 给定一些区间（活动），每个区间有左端点和右端点（开始时间和终止时间），要求找到最多的不相交区间（活动）。 以下按“活动安排问题”来解释。 这个问题的目的是求最多活动数量，所以持续时间长的活动不受欢迎，受欢迎的是尽快结束的、持续时间短的活动。 考虑以下3种贪心策略: （1） 最早开始时间。先选最早开始的活动a，当a结束后，再选下一个最早开始的活动。这种策略不好，因为它没有考虑活动的持续时间。假如a一直不结束，那么其他活动就不能开始。 （2） 最早结束时间。先选最早结束的活动a，当a结束后，再选下一个最早结束的活动。这种策略是合理的。越早结束的活动，越能腾出后续时间容纳更多的活动。 （3） 用时最少。先选时间最短的活动a，再选不冲突的下一个时间最短的活动。这个策略似乎可行，但是很容易找到反例，证明这个策略不正确。 图5.7活动安排 图5.7所示的例子，用“策略（1）最早开始时间”，选3; 用“策略（2）最早结束时间”，选1、2、5、6; 用“策略（3）用时最少”，选4、1、2。可见策略（2）的结果是最好的。 总结活动安排问题的贪心策略: 先按活动的结束时间（区间的右端点）排序，然后每次选结束最早的活动，并保证选择的活动不重叠。 例5.13线段覆盖https://www.luogu.com.cn/problem/P1803 问题描述: 有n个比赛，每个比赛的开始、结束的时间点已知。yyy想知道他最多能参加几个比赛。yyy要参加一个比赛必须善始善终，而且不能同时参加两个及以上的比赛。 输入: 第一行是一个整数n，接下来n行，每行是两个整数 Li、Ri(Li 2using namespace std; 3struct data{ 4 int L， R;//开始时间、结束时间 5}a［1000005］; 6bool cmp(data x，data y){return x.R> n; 9 for(int i=0;i>a［i］.L>>a［i］.R; 10 sort(a，a n，cmp); 11 int ans = 0; 12 int lastend = -1; 13 for(int i=0;i=lastend) { 15ans ; 16lastend = a［i］.R; 17} 18 cout请读者用图5.8所示的例子模拟合并过程。 4. 区间覆盖问题 给定一个目标大区间和一些小区间，问最少选择多少小区间可以覆盖大区间。 贪心策略: 尽量找出右端点更远的小区间。 操作步骤: 先对小区间的左端点排序，然后依次枚举每个小区间，在所有能覆盖当前目标区间右端点的区间中选择右端点最大的区间。 图5.9区间覆盖 在图5.9中，求最少用几个小区间能覆盖整个区间。先按左端点排序。设当前覆盖到了位置R，选择的小区间的数量为cnt。 从区间1开始，R的值是区间1的右端点A，R=A。cnt=1。 找到能覆盖R=A的区间2、3，在区间2、3中选右端点更远的3，更新R为区间3的右端点B，R=B。cnt=2。 区间4不能覆盖R=B，跳过。 找到能覆盖R=B的区间5，更新R=C。cnt=3。结束。 例5.14区间覆盖(加强版)https://www.luogu.com.cn/problem/P2082 问题描述: 已知有n个区间，每个区间的范围是［Li，Ri］，请求出区间覆盖后的总长。 输入: 第一行是一个整数n，接下来n行，每行是两个整数Li、Ri(Li 2using namespace std; 3typedef long long ll; 4struct data{ 5 ll L，R; 6} a［100005］; 7bool cmp(data x，data y){return x.L < y.L;} //按左端点排序 8int main(){ 9 int n; cin>>n; 10 for (int i=0;i>a［i］.L>>a［i］.R; 11 sort(a，a n，cmp); 12 ll lastend=-1，ans=0; 13 for (int i=0;i=lastend){ 15ans = a［i］.R - max(lastend，a［i］.L) 1; 16lastend = a［i］.R 1; 17} 18 cout< 2using namespace std; 3int main(){ 4 string s; cin >> s; 5 int ans = 0; 6 for(int i = 0; i < s.size() - 1;i ) { 7if(s［i］ == s［i 1］) { 8ans ; 9i ; 10} 11else if(s［i］ == ‘?’ || s［i 1］ == ‘?’) { 12ans ; 13i ; 14} 15 } 16 cout << ans; 17 return 0; 18} 例5.16买二赠一https://www.lanqiao.cn/problems/3539/learning/ 问题描述: 某商场有N件商品，其中第i件商品的价格是Ai。现在该商场正在进行“买二赠一” 的优惠活动，具体规则是每购买两件商品，假设其中较便宜的价格是P（如果两件商品的价格一样，则P等于其中一件商品的价格），就可以从剩余商品中任选一件价格不超过P/2（向下取整）的商品，免费获得这一件商品。可以通过反复购买两件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。小明想知道如果要拿下所有商品（包含购买和免费获得），至少要花费多少钱？ 输入: 第一行包含一个整数N。第二行包含N个整数，代表A1，A2，A3，…，AN。 输出: 输出一行，包含一个整数，表示答案。 评测用例规模与约定: 对于30%的测试用例，1≤N≤20； 对于100%的测试用例，1≤N≤5×105，1≤Ai≤109。 输入样例: 7 1 4 2 8 5 7 1 输出样例: 25 样例说明: 小明可以先购买价格为4和8的商品，免费获得一件价格为1的商品; 然后购买价格为5和7的商品，免费获得价格为2的商品; 最后单独购买剩下的一件价格为1的商品。总计花费4 8 5 7 1=25，不存在花费更低的方案。 最贵的商品显然不能免单，在购买了两个不能免单的最贵的商品后获得一个免单机会，那么这个免单机会给谁呢？给能免单的最贵的那个商品。这个贪心思路显然是对的。 以样例为例，先排序得{8 7 5 4 2 1 1}。先购买最贵的8、7，然后可以免单的最贵的是2。再购买剩下的最贵的5、4，免单1。最后单独买1。总价是25。 需要查找价格为P/2的商品，由于价格已经排序，可以用二分法加快查找的时间。 这里直接用二分法的库函数lower_bound()查找，请读者自行了解lower_bound()函数并熟悉它的应用。 1#include 2using namespace std; 3const int N = 5e5 10; 4int a［N］; 5bool vis［N］;//vis［i］=1表示已经免单了 6int main(){ 7 int n; scanf(”%d”， &n); 8 for(int i = 0; i < n; i ) scanf(”%d”， &a［i］); 9 sort(a， a n); 10 long long ans = 0; 11 int cnt = 0; 12 int last = -1; //购买的两件商品中便宜的那件 13 int last_id = n-1; //能免单的位置 14 for(int i = n-1; i >= 0; i--){ 15if(!vis［i］) 16cnt ， ans = a［i］， last = a［i］;//last是购买的第2件商品 17if(cnt == 2){//买了两件 18cnt = 0; 19int x = lower_bound(a ， a last_id， last / 2) - a; 20//找能免单的商品a［x］ 21if(x > last_id || a［x］ > last / 2) x--; //向下取整 22if(x>=0){ 23vis［x］ = 1; //x免单了 24last_id = x-1; //后面能免单的区间范围是［0，last_id］ 25} 26} 27 } 28 cout< 2using namespace std; 3int a［105］;//存硬币面值 4int main(){ 5 int x，n; cin >> x >>n; 6 for(int i=0;i> a［i］; 7 sort(a，a n); 8 if(a［0］!=1){cout<<-1; return 0;} //无解 9 int s=0，ans=0; 10 while(s=0;v--) 12if(a［v］<=s 1) {//找到［1，s］内的最大面值硬币a［v］ 13s =a［v］; //扩展s 14ans ; 15break; 16} 17 cout << ans; 18} 例5.18最大团http://oj.ecustacm.cn/problem.php?id=1762 问题描述: 数轴上有n个点，第i个点的坐标为xi，权值为wi。两个点i、j之间存在一条边当且仅当abs(xi-xj)≥wi wj时。请求出这张图的最大团的点数。团是两两之间存在边的定点集合。 输入: 输入的第一行为n，n≤200000。接下来n行，每行两个整数xi、wi，0≤|xi|，wi≤109。 输出: 输出一行，包含一个整数，表示最大团的点数。 输入样例: 4 2 3 3 1 6 1 0 2 输出样例: 3 最大团是一个图论问题: 在一个无向图中找出一个点数最多的完全子图。所谓完全图，就是图中所有的点之间都有边。n个点互相连接，共有n(n-1)/2条边。 普通图上的最大团问题是NP问题，计算复杂度是指数级的。例如常见的BronKerbosch算法是一个暴力搜索算法，复杂度为O(3n/3)。所以如果出最大团的题目，一般不会在普通图上求最大团，而是在一些特殊的图上，用巧妙的、非指数复杂度的算法求最大团。本题n≤200000，只能用复杂度小于O(nlog2n)的巧妙算法。 本题的图比较特殊，所有的点都在一条直线上。在样例中，存在的边有(03)、(06)、(26)、(36)，其中{0，3，6}这3点之间都有边，它们构成了一个最大团。 另外，本题对边的定义也很奇怪: “两个点i、j之间存在一条边当且仅当abs(xi-xj)≥wi wj时”。 考虑以下两个问题: （1） 哪些点之间有边？题目的定义是abs(xi-xj)≥wi wj，若事先把x排了序，设xj≥xi，移位得xj-wj≥xi wi。这样就把每个点的x和w统一起来，方便计算。 （2） 哪些点构成了团？是最大团吗？考察3个点x1≤x2≤x3，若x1和x2有边，则应有x1 w1≤x2-w2; 若x2和x3有边，则x2 w2≤x3-w3。推导x1和x3的关系: x1 w1≤x2-w2≤x2 w2≤x3-w3，即x1 w1≤x3-w3，说明x1和x3也有边。x1、x2、x3这3个点之间都有边，它们构成了一个团。依次这样操作，符合条件的x1，x2，x3……构成了一个团。但是用这个方法得到的团是最大的吗？ 为了方便思考，把上述讨论画成图，如图5.10所示。 图5.10最大团建模 把每个点的信息画成线段，左端点是x-w，右端点是x w。问题建模为: 在n个线段中找出最多的线段，使得它们互相不交叉。 读者学过贪心，发现它是经典的“活动安排问题”，或者称为“区间调度问题”，即在n个活动中安排尽量多的活动，使得它们互相不冲突。它的贪心解法如下: （1） 按活动的结束时间排序。本题按x w排序。 （2） 选择第一个结束的活动，跳过与它时间冲突的活动。 （3） 重复（2），直到活动为空。每次选择剩下活动中最早结束的活动，并跳过与它冲突的活动。 下面代码的计算复杂度： 排序为O(nlog2n)，贪心为O(n)，总复杂度为O(nlog2n)。 1#include 2using namespace std; 3const int N = 200005; 4struct aa{int l， r;} a［N］; 5bool cmp(const aa &a，const aa &b){return a.r=R){ 17R = a［i］.r; 18ans ; 19} 20 printf(”%d”，ans); 21 return 0; 22} 例5.19奶牛优惠券https://www.luogu.com.cn/problem/solution/P3045 问题描述: 农夫约翰需要新鲜奶牛。目前有N头奶牛出售，农夫的预算只有M元，奶牛i花费Pi。但是农夫有K张优惠券，当对奶牛i使用优惠券时只需要花费Ci（Ci≤Pi）。每头奶牛只能使用一张优惠券。求农夫最多可以养多少头牛？ 输入: 第一行3个正整数N、K、M，1≤N≤50000，1≤M≤1014，1≤K≤N。接下来N行，每行两个整数Pi和Ci，1≤Pi≤109，1≤Ci≤Pi。 输出: 输出一个整数，表示答案。 输入样例: 4 1 7 3 2 2 2 8 1 4 3 输出样例: 3 题意简述如下: 有n个数，每个数可以替换为较小的数; 从n个数中选出一些数，在选的时候允许最多替换k个，要求这些数相加不大于m，问最多能选出多少个数。 这个问题可以用女生买衣服类比。女生带着m元去买衣服，目标是尽量多买几件，越多越好。每件衣服都有优惠，但是必须使用优惠券，一件衣服只能用一张。衣服的优惠幅度不一样，有可能原价贵的优惠后反而更便宜。女生有k张优惠券，问她最多能买多少件衣服。 男读者可以问一问女朋友，她会怎么买衣服。聪明的她可能马上问: 优惠券是不是无限多？如果优惠券用不完，那么衣服的原价形同虚设，按优惠价从小到大买就行。可惜，优惠券总是不够用。 她想出了这个方法: 按优惠价排序，先买优惠价便宜的，直到用完优惠券; 如果还有钱，再买原价便宜的。 但是这个方法不是最优的，因为优惠价格低的可能优惠幅度小，导致优惠券被浪费了。例如: 衣服: a，b，c，d，e 优惠价: 3，4，5，6，7 原价: 4，5，6，15，10 设有m=20元，k=3张优惠券。把3张优惠券用在a、b、c上并不是最优的，这样只能买3件。最优解是买4件: a、b、d用优惠价，c用原价，共19元。 下面对这个方法进行改进。既然有优惠幅度很大的衣服，就试一试把优惠券转移到这件衣服上，看能不能获得更大的优惠。把这次转移称为“反悔”。 设优惠价最便宜的前k件衣服用完了k张优惠券。现在看第i=k 1件衣服，要么用原价买，要么转移一张优惠券过来用优惠价买，看哪种结果更好。设原价是p，优惠价是c。 在反悔之前，第i件用原价pi买，前面第j件用优惠价cj买，共花费: tot pi cj，其中tot是其他已经买的衣服的花费 在反悔后，第j件把优惠券转移给第i件，改成原价pj，第i件用优惠价ci，共花费: tot ci pj 如果反悔更好，则有: tot pi cjp1-c2，说明替换优惠券不值得，不用替换。下一件衣服用原价买p1。 ② 若d≤p1-c2，说明替换优惠券值得，下一件衣服用优惠价买c2，原来用优惠券的改成用原价。 本题总体上是贪心，用3个优先队列处理贪心。但是优惠券的替换操作是贪心的“反悔”，所以称为“反悔贪心”。贪心是连续做局部最优操作，但是有时局部最优推不出全局最优，此时可以用反悔贪心，撤销之前做出的决策，换条路重新贪心。 1//代码参考 https://www.luogu.com.cn/blog/Leo2007-05-24/solution-p3045 2#include 3using namespace std; 4#define int long long 5const int N=50010; 6int p［N］，c［N］; 7bool buy［N］;//buy［i］=1: 第i个物品被买了 8int ans=0; 9priority_queue，vector >，greater > >P，C; 10priority_queue，greater >D; 11signed main(){ 12 int n，k，m; cin>>n>>k>>m; 13 for(int i=1;i<=n;i ){ 14cin>>p［i］>>c［i］; 15P.push(make_pair(p［i］，i)); 16//原价，还没买的在这里，如果买了就弹出去 17C.push(make_pair(c［i］，i)); 18//优惠价，还没买的在这里，如果买了就弹出去 19 } 20 for(int i=1;i<=k;i ) 21D.push(0);//k张优惠券，开始时每个的优惠为0 22 while(!P.empty() && !C.empty()){ 23pair p1 = P.top();//取出原价最便宜的 24pair c2 = C.top();//取出优惠价最便宜的 25if(buy［p1.second］){ 26P.pop(); continue;//这个已经买了，跳过 27} 28if(buy［c2.second］){ 29C.pop(); continue;//这个已经买了，跳过 30} 31if(D.top() > p1.first-c2.first){ 32//用原价买i更划算，不用替换优惠券 33m -= p1.first;//买原价最便宜的 34P.pop();//这里不要C.pop()，因为买的是p1，不是c2 35buy［p1.second］ = true;//标记p1买了 36 } 37 else{//替换优惠券。前k个都先执行这里 38m -= c2.first D.top(); //买优惠价最便宜的 39C.pop();//这里不要p.pop()，因为买的是c2，不是p1 40buy［c2.second］=true;//标记c2买了 41D.pop();//原来用优惠券的退回优惠券 42D.push(p［c2.second］-c［c2.second］); 43//c2使用优惠券，重新计算delta并进队列 44} 45if(m >=0) ans ; 46else break; 47 } 48 cout<49 return 0; 50} 51 【练习题】 lanqiaoOJ: 三国游戏3518、平均3532、答疑1025、身份证3849、找零钱3854、01搬砖2201、卡牌游戏1057、寻找和谐音符3975、小蓝的旅行计划3534、翻硬币209、防御力226。 洛谷: 排座椅P1056、母舰P2813、排队接水P1223、小A的糖果P3817、加工生产调度P1248、负载平衡问题P4016。 5.6扩 展 学 习 从本章开始进入了算法学习阶段。本章的“基本算法”是一些“通用”的算法，可以在很多场景下应用。 在本书第2章的“2.1 杂题和编程能力”一节曾提到计算思维的作用，通过做杂题可以帮助大家建立基本的、自发的计算思维。在计算机科学中有大量经典的算法和数据结构，它们代表了计算机科学中最璀璨的花朵。在这些知识点中，基本算法易于理解、适用面广、精巧高效，是计算思维的奠基，真正的计算思维从这里开始。 除了本章介绍的前缀和、差分、二分、贪心，基本算法还有尺取法、倍增法、离散化、分治等，在逐渐深入学习算法的过程中，这些基本算法都是必须掌握的知识点。

書城介紹　 |　合作申請　|　索要書目　 |　新手入門　|　聯絡方式　 |　幫助中心　|　找書說明　 |　送貨方式　|　付款方式	台灣用户　|　香港/海外用户
megBook.com.tw
Copyright (C) 2013 - 2024 （香港）大書城有限公司　All Rights Reserved.