第5章〓基本算法

基本算法没有复杂的逻辑和步骤，但是计算效率高、应用场景丰富，是算法竞赛必考的知识点。


在算法竞赛中有一些“通用”的算法，例如尺取法、二分法、倍增法、前缀和、差分、离散化、分治、贪心等。这些算法没有复杂的逻辑，代码也简短，但是它们的应用场合多，效率也高，广泛应用在编程和竞赛中。在蓝桥杯大赛中，这些算法几乎是必考的。本章介绍前缀和、差分、二分、贪心。




5.1算法与算法复杂度
在前面几章讲解例题时有很多题分析了“算法复杂度”，使读者对算法分析有了一定的了解。进行算法分析是做竞赛题时的一个必要步骤，用于评估问题的难度和决定使用什么算法来求解。在蓝桥杯这种赛制中，一道题往往可以用多种算法求解，例如较差算法可以通过30%的测试，中等算法可以通过70%的测试，优秀算法可以通过100%的测试。

本节回答两个基本问题： 什么是算法？如何评估算法？

5.1.1算法的概念

“程序=算法+数据结构”。算法是解决问题的逻辑、方法、过程，数据结构是数据在计算机中的存储和访问方式，两者紧密结合解决复杂问题。

算法(Algorithm)是对特定问题求解步骤的一种描述，是指令的有限序列。它有5个特征： 

(1) 输入。一个算法有零个或多个输入。程序可以没有输入，例如一个定时闹钟程序，它不需要输入，但是能够每隔一段时间就输出一个报警。

(2) 输出。一个算法有一个或多个输出。程序可以没有输入，但是一定要有输出。

(3) 有穷性。一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成。

(4) 确定性。算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。

(5) 可行性。算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

5.1.2计算资源

计算机软件运行需要计算时间和存储空间两种资源。资源是有限的，一个算法对这两种资源的使用程度可以用来衡量该算法的优劣。

时间复杂度： 代码运行需要的时间。

空间复杂度： 代码运行需要的存储空间。

与这两个复杂度对应，程序设计题会给出对运行时间和空间的说明，例如“时间限制： 1s，内存限制： 256MB”，参赛队员提交到判题系统的代码需要在1s内运行结束，且使用的空间不能超过256MB。若有一个不满足，就判错。

这两个限制条件非常重要，是检验代码性能的参数，所以队员拿到题目后第一步需要分析代码运行需要的计算时间和存储空间。

如何衡量代码运行的时间？通过代码打印运行时间可以得到一个直观的认识。

下面的Python代码只有一个for语句，代码对k累加n次，最后打印运行时间。




1from time import *
2k = 0
3n = 10**7# 一千万
4s = process_time()             # 开始时间
5for i in range(n):  k += 5     # 循环n次
6t = process_time()             # 终止时间
7print(t - s)                   # 打印运行时间



在作者的笔记本式计算机上运行，循环n=一千万次，用时1.29s。换了一台台式计算机，用时0.234375s。Python的for循环很耗时，比C++的循环慢很多。Python的编程题一般给10s的测试时间，此时代码只能做千万次左右的循环。

竞赛评测用的判题服务器(OJ系统)，性能可能比这个好一些，也可能差不多。对于C++题目，如果题目要求“时间限制： 1s”，那么内部的循环次数n应该在一亿次以内，Java也在一亿次以内。对于同等规模的Python题目，时间限制一般是5~10s。

由于代码的运行时间依赖于计算机的性能，不同的计算机结果不同，所以直接把运行时间作为判断标准并不准确，用代码执行的“计算次数”来衡量更加合理。例如上述代码循环了n次，把它的运行次数记为O(n)，O称为计算复杂度的“大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=107时，log2n<24。

(3) O(n)，线性时间。计算时间随规模n线性增长。在很多情况下，这是算法可能达到的最优复杂度，因为对输入的n个数，程序一般需要处理所有的数，即计算n次。例如查找一个无序数列中的某个数，可能需要检查所有的数。再例如图问题，有V个点和E条边，大多数图的问题，都需要搜索所有的点和边，复杂度的最优上限是O(V+E)。

(4) O(nlog2n)。这常是算法能达到的最优复杂度。例如分治法，一共O(log2n)个步骤，每个步骤对每个数操作一次，所以总复杂度是O(nlog2n)。例如n=106时，nlog2n=2×107。

(5) O(n2)。一个两重循环的算法，复杂度是O(n2)。类似的复杂度有O(n3)、O(n4)等。

(6) O(2n)。一般对应集合问题，例如一个集合中有n个数，这些数不分先后，子集共有2n个。

(7) O(n!)。一般对应排列问题。如果集合中的数分先后，按顺序输出所有的排列，共有O(n!)个。

把上面的复杂度分成两类： 多项式复杂度，包括O(1)、O(n)、O(nlog2n)、O(nk)等，其中k是一个常数； 指数复杂度，包括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<n。

输出： 输出一个整数，表示最小的和。

输入样例：  

5 1

2 5 1 10 6
输出样例： 

3



第一步肯定是排序，例如从小到大排序，然后再进行两种操作。操作(1)在a［］的尾部选一个数，操作(2)在a［］的头部选两个数。

大家容易想到一种简单方法： 每次在操作(1)和操作(2)中选较小的值。这是贪心法的思路。用贪心法对吗？分析之后发现用贪心法是错误的，例如{3, 1, 1, 1, 1, 1, 1}，做k=3次操作，如果每次都按贪心法，就是做3次操作(2)，结果是6，但是正确答案是做3次操作(1)，结果是5。

重新考虑所有可能的情况。设操作(2)做p次，操作(1)做k-p次，求和： 

∑2pi=1ai+∑ni=n+p－k+1ai

为了找最小的和，需要把所有的p都试一遍。如果直接按上面的公式计算，那么验证一个p的计算量是O(n)，验证所有的p，1≤p≤k，总计算量为O(kn)，超时。

大家容易发现公式的两个部分就是前缀和，分别等于sum［2p］、sum［n］-sum［n+p-k］。如果提前算出前缀和sum［］，那么验证一个p的计算量是O(1)，验证所有p的总计算量是O(n)。

下面是Python代码。对于代码的计算复杂度，第3行sort()是O(nlog2n)，第5、7行的for循环都是O(n)，总复杂度为O(nlog2n)。




1n, k = map(int, input().split())
2b = list(map(int, input().split()))
3a = ［0］ + sorted(b)# a［0］不用，从a［1］开始
4s = ［0］ * (n+1)         # 前缀和
5for i in range(1, n+1):  s［i］ = s［i-1］ + a［i］
6ans = 10**18
7for p in range(1, k+1):
8ans = min(s［n］ - s［n+p-k］ + s［2*p］, ans)
9print(ans)



再看一道简单题。






 例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#pypy
2n = int(input())
3a = list(map(int, input().split()))
4sum = ［0］ * (n + 1)# 前缀和
5for i in range(1, n + 1):
6sum［i］ = sum［i - 1］ + a［i - 1］    # 求前缀和
7ans = sum［n］
8for i in range(1, n + 1):             # 较大的和最小是多少
9ans = min(ans, max(sum［i］, sum［n］ - sum［i］))
10print(ans)



下面的例题是前缀和在异或计算中的应用，这也是其常见的应用场景。






 例5．3
2023年第十四届蓝桥杯省赛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。



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个子段。

下面Python代码的第4、5行遍历所有的子段［L, R］，第7行求［L, R］的子段和，共3重for循环，计算复杂度为O(n3)，只能通过30%的测试。




1n = int(input())
2a = list(map(int, input().split()))
3ans = 0
4for L in range(n):# 遍历所有区间［L,R］
5for R in range(L, n):
6sum = 0
7for i in range(L, R+1):    # 子段和
8sum ^= a［i］
9ans += sum      # 累加所有子段和
10print(ans)



(2) 通过60%的测试。

本题可以用前缀和优化。

记异或和a1a2…ai为

si= a1a2…ai

这里si是异或形式的前缀和，这样就把复杂度为O(n)的子段异或和计算a1a2…ai优化为O(1)的求si的计算。

以包含a1的子段为例，这些子段的异或和相加，等于

a1+a1a2+…+a1…ai+…+a1…an= s1+s2+…+si+…+sn

前缀和的计算用递推得到。普通前缀和的递推公式为s［i］=s［i-1］+a［i］，异或形式的前缀和的递推公式为s［i］=s［i-1］ ^ a［i］，下面代码中用这个公式的简化形式求解了前缀和。

Python代码的计算复杂度是多少？第4行和第6行用两重循环遍历所有的子段，同时计算前缀和，计算复杂度是O(n2)，可以通过60%的测试。




1n = int(input())
2a = list(map(int, input().split()))
3ans = 0
4for L in range(n):
5sum = 0# sum是包含a［L］的子段的前缀和
6for R in range(L, n):
7sum ^= a［R］        # 用递推求前缀和sum
8ans += sum         # 累加所有子段和
9print(ans)



(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位。下面代码的第4行逐个计算20位的每一位，第7行的for循环计算n个前缀和，总计算量约为20×n。




1n = int(input())
2a = ［int(x) for x in input().split()］
3ans = 0
4for k in range(21):# 所有a都不超过20位
5zero, one = 1, 0           # 统计第k位的0和1的数量
6cnt, sum = 0, 0            # cnt用于统计第k位有多少对sisj =1
7for i in range(n):
8v = (a［i］ >>k) & 1    # 取a［i］的第k位
9sum ^= v      # 对所有a［i］的第k位做异或得到sum，sum等于0或者1
10if sum == 0:           # 前缀和为0
11zero += 1          # 0的数量加1
12cnt += one  # 这次sum=0，这个sum跟前面等于1的sum异或得1
13else:                  # 前缀异或为1
14one += 1           # 1的数量加1
15cnt += zero # 这次sum=1，这个sum跟前面等于0的sum异或得1
16ans += cnt * (1 << k)      # 第k位的异或和相加
17print(ans)



前面的例子都是一维数组上的前缀和，下面介绍二维数组上的前缀和。






 例5．4
领地选择 https://www.luogu.com.cn/problem/P2004


问题描述： 作为在虚拟世界里统率千军万马的领袖，小Z认为天时、地利、人和三者是缺一不可的，所以谨慎地选择首都的位置对于小Z来说是非常重要的。首都被认为是一个占地c×c的正方形。小Z希望寻找到一个合适的位置，使得首都所占领的位置的土地价值和最高。

输入： 第一行有3个整数n、m、c，表示地图的宽和长以及首都的边长。接下来n行，每行m个整数，表示地图上每个地块的价值，价值可能为负数。

数据范围： 对于60%的数据，n, m≤50； 对于90%的数据，n, m≤300； 对于100%的数据，1≤n,m≤103,1≤c≤min(n, m)。

输出： 一行两个整数x、y，表示首都左上角的坐标。

输入样例：  

3 4 2

1 2 3 1

-1 9 0 2

2 0 1 1
输出样例： 

1 2





概括题意： 在n×m的矩形中找一个边长为c的正方形，把正方形内所有坐标点的值相加，使价值最大。

简单的做法是枚举每个坐标，作为正方形的左上角，然后计算出边长c内所有地块的价值和，找到价值和最大的坐标。时间复杂度为O(nmc2)，能通过60%的测试。请读者练习。

本题是二维前缀和的直接应用。

一维前缀和定义在一维数组a［］上： sum［i］=a［1］+a［2］+…+a［i］。

把一维数组a［］看成一条直线上的坐标，前缀和就是所有坐标值的和，如图5.1所示。



图5.1一维数组a［］在直线上


二维前缀和是一维前缀和的推广。设二维数组a［］［］有1~n行、1~m列，二维前缀和如下： 


sum［i］［j］=a［1］［1］+a［1］［2］+a［1］［3］+…+a［1］［j］+

a［2］［1］+a［2］［2］+a［2］［3］+…+a［2］［j］+…+

a［i］［1］+a［i］［2］+a［i］［3］+…+a［i］［j］


把a［i］［j］的(i,j)看成二维平面的坐标，那么sum［i］［j］就是左下角坐标(1,1)和右上角坐标(i,j)围成的方形中所有坐标点的和，如图5.2所示。


图5.2二维数组和二维平面



二维前缀和sum［］［］存在以下递推关系： 

sum［i］［j］=sum［i-1］［j］+sum［i］［j-1］-sum［i-1］［j-1］+a［i］［j］

根据这个递推关系，用两种for循环可以计算出sum［］［］。

对照图5.2理解这个公式，sum［i-1］［j］是坐标(1,1)~(i-1, j)内所有的点，sum［i］［j-1］是(1,1)~(i, j-1)内所有的点，两者相加，其中sum［i-1］［j-1］被加了两次，所以要减去一次。

下面的Python代码中第7行让sum［］［］和a［］［］共用，从而节省一半空间，否则提交判题系统会超出空间限制。




1n, m, c = map(int, input().split())
2a = ［［0］ * (m + 1) for _ in range(n + 1)］
3for i in range(1, n + 1):
4row = list(map(int, input().split()))
5for j in range(1, m + 1):
6a［i］［j］ = row［j - 1］
7a［i］［j］ = a［i-1］［j］ + a［i］［j-1］ - a［i-1］［j-1］ + a［i］［j］
8# 上一行等于 s［i］［j］ = s［i-1］［j］ + s［i］［j-1］ - s［i-1］［j-1］ + a［i］［j］
9Max = float('-inf')
10x = 0
11y = 0
12for x1 in range(1, n - c + 2):
13for y1 in range(1, m - c + 2):# 枚举所有坐标点
14x2 = x1 + c - 1
15y2 = y1 + c - 1              # 正方形的右下角坐标
16ans = a［x2］［y2］ - a［x2］［y1-1］ - a［x1-1］［y2］ + a［x1-1］［y1-1］
17if ans >Max:
18Max = ans
19x = x1
20y = y1
21print(x, y)






5.3差分
前缀和的主要应用是差分，差分是前缀和的逆运算。

5.3.1一维差分

与一维数组a［］对应的差分数组d［］的定义如下： 

d［k］=a［k］-a［k-1］

即差分数组d［］是原数组a［］的相邻元素的差。根据d［］的定义，可以反过来推出： 

a［k］=d［1］+d［2］+…+d［k］

即a［］是d［］的前缀和，所以“差分是前缀和的逆运算”。

为了方便理解，把每个a［］看成直线上的坐标，把每个d［］看成直线上的小线段，它的两端是相邻的a［］，如图5.3所示。将这些小线段相加，就得到了从起点开始的长线段a［］。




图5.3把每个d［］看成小线段，把每个a［］看成从a［1］开始的小线段的和


差分是一种巧妙且简单的方法，它应用于区间的修改和查询问题。把给定的数据元素集A分成很多区间，对这些区间做很多次操作，每次操作是对某个区间内的所有元素做相同的加减操作，若一个一个地修改这个区间内的每个元素，复杂度是O(n)，非常耗时。引入“差分数组”，当修改某个区间时，只需要修改这个区间的“端点”，就能记录整个区间的修改，而对端点的修改非常快，复杂度是O(1)。当所有的修改操作结束后，再使用差分数组，计算出新的A。

为什么使用差分数组能提升修改的效率？如何把O(n)的区间操作优化为O(1)的端点操作？

将区间［L, R］内的每个元素a［］加上v，只需要把对应的d［］做以下操作。

(1) 把d［L］加上v： d［L］ += v。

(2) 把d［R+1］减去v： d［R+1］ -= v。

使用d［］，能精确地实现只修改区间内元素的目的，而不会修改区间外的a［］值。根据前缀和a［x］=d［1］+d［2］+…+d［x］，有

(1) 1≤x<L，前缀和a［x］不变。

(2) L≤x≤R，前缀和a［x］增加了v。

(3) R<x≤N，前缀和a［x］不变，因为被d［R+1］中减去的v抵消了。

每次操作只需要修改区间［L, R］的两个端点的d［］值，复杂度是O(1)。经过这种操作后，原来直接在a［］上做的复杂度为O(n)的区间修改操作就变成了在d［］上做的复杂度为O(1)的端点操作。在完成区间修改并得到d［］后，最后用d［］计算a［］，复杂度是O(n)。m次区间修改和一次查询，总复杂度为O(m+n)，比暴力法的O(mn)好多了。 

数据A可以是一维的线性数组a［］、二维矩阵a［］［］、三维立体a［］［］［］。相应地，定义一维差分数组D［］、二维差分数组D［］［］、三维差分数组D［］［］［］。






 例5．5
重新排序 lanqiaoOJ 2128


问题描述： 给定一个数组A和一些查询Li, Ri，求数组中第Li至第Ri个元素的和。







小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使最终每个查询结果的和尽可能的大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少? 

输入： 输入的第一行包含一个整数n。第二行包含n个整数A1、A2、……、An，相邻两个整数之间用一个空格分隔。第三行包含一个整数m，表示查询的数目。接下来的m行，每行包含两个整数Li、Ri，相邻两个整数之间用一个空格分隔。

输出： 输出一行，包含一个整数，表示答案。

输入样例：  

5

1 2 3 4 5

2

1 3

2 5输出样例： 

4






评测用例规模与约定： 
对于30%的评测用例，n,m≤50； 对于50%的评测用例，n,m≤500； 对于70%的评测用例，n,m≤5000； 对于所有评测用例，1≤n,m≤105，1≤Ai≤106，1≤Li≤ Ri≤n。


本题的m个查询可以统一处理，在读入m个查询后，每个a［i］被查询了多少次就知道了。用cnt［i］记录a［i］被查询的次数，cnt［i］*a［i］就是a［i］对总和的贡献。

下面分别给出通过70%和100%测试的两种解法。

(1) 通过70%的测试。

下面代码的第11行先计算出cnt［］，第13行计算出原数组上的总和ans1。

然后计算新数组上的总和。显然，把查询次数最多的数分给最大的数，对总和的贡献最大。对a［］和cnt［］排序，把最大的a［n］与最大的cnt［n］相乘、次大的a［n-1］与次大的cnt［n-1］相乘，等等。代码的第17行计算出新数组上的总和ans2。

代码的主要计算是第8行和第10行的for循环，复杂度为O(mn)，该代码只能通过70%的测试。




1N = 100003
2a = ［0］ * N
3cnt = ［0］ * N
4n = int(input())
5a［1:n+1］ = map(int, input().split())# a［0］不用，从a［1］开始
6m = int(input())
7ans1,ans2 = 0,0       # ans1：原区间和；ans2： 新区间和
8for _ in range(m):
9L, R = map(int, input().split())
10for i in range(L, R+1):
11cnt［i］ += 1            # 第i个数被加了一次，累计加了多少次
12for i in range(1, n+1):
13ans1 += a［i］ * cnt［i］        # 在原数组上求区间和
14a［1:n+1］ = sorted(a［1:n+1］)      # a［0］不用，从a［1］开始
15cnt［1:n+1］ = sorted(cnt［1:n+1］)  # cnt［0］不用，从cnt［1］开始
16for i in range(1, n+1):
17ans2 += a［i］ * cnt［i］
18print(ans2 - ans1)




(2) 通过100%的测试。

本题是差分优化的直接应用。

前面提到，通过70%测试的代码效率低的原因是第11行计算cnt［］。根据差分的应用场景，每次查询的［L, R］就是对a［L］~a［R］中的所有数的累加次数加1，也就是对cnt［L］~cnt［R］中的所有cnt［］加1。那么对cnt［］使用差分数组d［］即可。

下面代码中第11、12行用差分数组d［］记录cnt［］的变化，第15行用d［］恢复得到cnt［］。其他部分和前面通过70%测试的代码一样。

在下面的代码中，第9行for循环的计算复杂度只有O(m)，最耗时的是第18、19行的排序，复杂度为O(nlog2n)，该代码能通过100%的测试。




1N = 100003
2a = ［0］ * N
3d = ［0］ * N
4cnt = ［0］ * N
5n = int(input())
6a［1:n+1］ = map(int, input().split())
7m = int(input())
8ans1, ans2 = 0, 0
9for _ in range(m):
10L, R = map(int, input().split())
11d［L］ += 1
12d［R+1］ -= 1
13cnt［0］ = d［0］
14for i in range(1, n+1):
15cnt［i］ = cnt［i-1］ + d［i］# 用差分数组d［］求cnt［］
16for i in range(1, n+1):
17ans1 += a［i］ * cnt［i］
18a［1:n+1］ = sorted(a［1:n+1］)
19cnt［1:n+1］ = sorted(cnt［1:n+1］)
20for i in range(1, n+1):
21ans2 += a［i］ * cnt［i］
22print(ans2 - ans1)



再看一道例题。






 例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行，每行包含两个整数1i和hi，表示第i列缺口的范围，0≤1i≤hi<N。

输出： 输出一个数字，表示答案。

输入样例： 

5 2

2 3

1 2

2 3

1 2

2 3
输出样例： 

2







箱子的高度为H，检查障碍物中的连续H行，看哪H行需要清理的障碍物最少，或者哪H行中的空白最多。在输入样例中，障碍物共5行，这5行中的空白数量从底部开始往上数分别是(0, 2, 5, 3, 0)，其中(5, 3)这两行的空白最多，是5+3=8，需要移除的障碍物的数量是N×H-8=5×2-8=2。

用数组a［］表示障碍物，a［i］是障碍物中第i行的空白数量。把题目抽象为： a［］是N个整数，从a［］中找出连续的H个整数，要求它们的和最大。

先考虑用暴力法求解。

(1) 如果用暴力法从左到右依次对a［］中的H个整数求和，找到最大的和，总计算量是O(NH)，超时。

(2) 需要注意输入的问题。题目按列给出空白数量，需要转换为行的空白数量。如果简单地转换，计算量太大。例如样例第1列的空白位置是(2, 3)，需要赋值a［2］++、a［3］++。一列有H个空白，a［］数组需要赋值H次，N列的总计算量是O(NH)，超时。

本题用差分与前缀和来优化。

(1) 用差分处理输入。下面代码中第6行读一个列的起点位置1i和终点位置hi，第7行和第8行输入d［］，d［］是a［］的差分，计算量仅为O(N)。

(2) 用前缀和求区间和。第10行用d［］求a［］； 第12行计算a［］的前缀和sum［］； 第15行找到最大的区间和。其计算量仅为O(N)。

上述题解的实现见下面的代码。代码可以进行空间优化，d［］、a［］、sum［］都用sum［］存储，见第7、8、10、12行的注释，请读者思考为什么可以这样做。当然，在一般情况下题目给的存储空间够大，不需要做这个优化。




1import sys
2input = sys.stdin.readline# 加这行后读入会快一些
3n, h = map(int, input().split())
4d, a, sum = ［0］ * (n+10), ［0］ * (n+10), ［0］ * (n+10)
5for i in range(1, n+1):
6li, hi = map(int, input().split())
7d［li］ += 1                         # 可替换为sum［li］++;
8d［hi+1］ -= 1                       # 可替换为sum［hi+1］--;
9for i in range(1, n+1):                # 用差分数组计算原数组
10a［i］ = a［i-1］ + d［i-1］             # 可替换为sum［i］ += sum［i-1］;
11for i in range(1, n+1):                # 用原数组计算前缀和数组
12sum［i］ = sum［i-1］ + a［i］           # 可替换为sum［i］ += sum［i-1］;
13ans = sum［h-1］
14for left in range(1, n-h+2):
15ans = max(ans, sum［left+h-1］ - sum［left-1］)
16print(n * h - ans)



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］。在图5.5中，每个格子的面积是一个D［］［］，例如阴影格子是D［i］［j］，它由(i-1, j)、(i, j)、(i-1, j-1)、(i, j-1)4个坐标点定义。坐标点(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］

这个公式可以通过图5.5来观察。阴影方格表示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．7
2023年第十四届蓝桥杯省赛Python大学C组试题F： 棋盘 lanqiaoOJ 3533 


时间限制： 10s 内存限制： 512MB 本题总分： 15分

问题描述： 小蓝有一个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) 模拟。

按题目的描述编码实现。第3、5、6行有三重for循环，计算复杂度为O(mn2)，只能通过30%的测试。




1n, m = map(int, input().split())
2a = ［［0］ * 2100 for _ in range(2100)］
3for _ in range(m):
4x1, y1, x2, y2 = map(int, input().split())
5for i in range(x1, x2+1):
6for j in range(y1, y2+1):
7a［i］［j］ ^= 1
8for i in range(1, n+1):
9for j in range(1, n+1):
10print(a［i］［j］, end="")
11print()



(2) 差分。通过100%的测试。

这是一道很直白的二维差分题。第5~8行是二维差分计算，其实改成注释中的写法也行，请读者思考。




1n, m = map(int, input().split())
2a = ［［0］ * (n + 2) for _ in range(n + 2)］
3d = ［［0］ * (n + 2) for _ in range(n + 2)］
4def insert(x1, y1, x2, y2):
5d［x1］［y1］ += 1# d［x1］［y1］ ^= 1
6d［x1］［y2+1］ -= 1    # d［x1］［y2+1］ ^= 1
7d［x2+1］［y1］ -= 1    # d［x2+1］［y1］ ^= 1
8d［x2+1］［y2+1］ += 1  # d［x2+1］［y2+1］ ^= 1
9for _ in range(m):
10x1, y1, x2, y2 = map(int, input().split())
11insert(x1, y1, x2, y2)
12for i in range(1, n + 1):
13for j in range(1, n + 1):
14a［i］［j］ = d［i］［j］ + a［i - 1］［j］ + a［i］［j - 1］ - a［i - 1］［j - 1］
15print(a［i］［j］ & 1, end="")
16print()



【练习题】

lanqiaoOJ： 灵能传输196、和与乘积1595、冒险岛3224、统计子矩阵2109、无线网络发射器选址374。

洛谷： 求区间和B3612、光骓者的荣耀P5638、dx分计算P10233、领地选择P2004、地毯P3397、最大加权矩形P1719、卡牌游戏P6625。




5.4二分
二分法是一种思路简单、编码容易、效率极高、应用广泛的算法。在任何算法竞赛中，二分法都是最常见的知识点之一。二分法的应用场景比前缀和更广泛。

二分法的思想很简单，每次把搜索范围缩小一半，直到找到答案为止。设初始范围是［L, R］，常见的二分法代码这样写： 




1while L < R:# 一直二分，直到区间［L,R］缩小到L=R
2mid = (L + R) // 2         # mid是L、R的中间值
3if check(mid):R = mid    # 答案在左半部分［L,mid］，更新R=mid
4else:L = mid + 1     # 答案在右半部分［mid+1,R］，更新L=mid+1



答案在区间［L, R］中，通过中间值mid缩小搜索范围。这样搜索答案： 

(1) 如果答案在左半部分，把范围缩小到［L, mid］，更新R=mid，然后继续。

(2) 如果答案在右半部分，把范围缩小到［mid+1, R］，更新L=mid+1，然后继续。

经过多次二分，最后范围缩小到L=R，这就是答案。

二分的效率极高，例如在230=10亿个数字中查找某个数，前提是这些数已经排序，然后用二分法来找，最多只需要找log2(230)=30次。二分法的计算复杂度是O(log2n)。

以猜数字游戏为例，一个［1, 100］内的数字，猜7次就能猜出来。例如猜数字68，如表5.2所示。



表5.2猜数字68




次数
原［L,R］
a［mid］
check()判断
更新［L,R］


1
［1,100］
50
小于或等于50吗？不
［51,100］
2
［51,100］
75
小于或等于75吗？是
［51,75］
3
［51,75］
63
小于或等于63吗？不
［64,75］
4
［64,75］
69
小于或等于69吗？是
［64,69］
5
［64,69］
66
小于或等于66吗？不
［67,69］
6
［67,69］
68
小于或等于68吗？是
［67,68］
7
［67,68］
67
小于或等于67吗？不
［68,68］


下面是代码实现。二分函数bin_search()操作3个变量： 区间左端点L、右端点R、二分的中位数mid。每次把区间缩小一半，把L或R更新为mid，直到L= R为止，即找到了答案所处的位置。




1def check(x, mid): return x <=a［mid］
2def bin_search(n, x):
3L, R = 1, n
4while L < R:
5mid = (L+R) // 2
6if check(x, mid):R = mid
7else:L = mid + 1
8return a［L］
9n = 100
10a = ［0］ * 105
11for i in range(1, n + 1):a［i］ = i
12x = 68
13print("x=", bin_search(n, x))



二分法把长度为n的有序序列上O(n)的查找时间优化到了O(log2n)。

注意，二分法的应用前提是序列是单调有序的，从小到大或从大到小。在无序的序列上无法二分，如果是乱序的，应该先排序再二分。

如果在乱序序列上只搜一次，不需要用二分法。如果用二分法，需要先排序，排序的复杂度为O(nlog2n)，再二分是O(log2n)，排序加二分的总复杂度为O(nlog2n)。如果用暴力法直接在乱序的n个数中查找，复杂度是O(n)，比排序加二分快。

如果不是搜一个数，而是搜m个数，那么先排序再做m次二分的计算复杂度是O(nlog2n+mlog2n)，而暴力法是O(mn)，当m很大时，二分法远远好于暴力法。

在做二分法题目时，需要建模出一个有序的序列，并且答案在这个序列中。在编程时，根据题目要求确定区间［L, R］范围，并写一个check()函数来更新L和R。

［L, R］的中间值mid有多种计算方法： 


mid = (L+R)/2

mid = (L+R)>>1

mid = L+(R-L)/2

5.4.1二分法的经典应用

二分法的经典应用场景是“最小值最大化(最小值尽量大)”和“最大值最小化(最大值尽量小)”。

1. 最小值最大化

以“牛棚问题”为例。有n个牛棚，分布在一条直线上，有k头牛，给每头牛安排一个牛棚住，k<n。由于牛的脾气很大，所以希望让牛之间尽量住得远一些。这个问题简化为： 在一条直线上有n个点，选k个点，其中某两点之间的距离是所有距离中最小的，求解目标是让这个最小距离尽量大。

这就是“最小值(两点间的最小距离)最大化”。

“牛棚问题”的求解可以用猜的方法。猜最小距离是D，看能不能在n个点中选k个，使得任意两点之间的距离≥D。如果可以，说明D是一个合法的距离。然后猜新的D，直到找到那个最大的合法的D。

具体操作是： 从第1个点出发，逐个检查后面的点，第一个距离≥D的点就是选中的第2点； 然后从第2点出发，再选后面第一个距离第2点≥D的点，这是选中的第3点； …继续下去，直到检查完n个点。这一轮猜测的计算复杂度是O(n)。

检查完n个点，如果选中的点的数量≥k，说明D猜小了，下次猜大一点； 如果选中的点的数量<k，说明D猜大了，下次猜小一点。

如何猜D？简单的办法是从小到大一个一个试，但是计算量太大了。

用二分法可以加速猜D的过程。设D的初值是一个极大的数，例如就是所有n个点的总长度L。接下来的二分操作和前面的“猜数字游戏”一样，经过O(log2L)次，就能确定D。

总计算量： 一共进行O(log2L)轮猜测，每一轮的计算量为O(n)，总计算量为O(nlog2L)。

2. 最大值最小化

经典的例子是“序列划分”问题。有一个包含n个正整数的序列，把它划分成k个子序列，每个子序列是原序列的一个连续部分，第i个子序列的和为Si。在所有s中有一个最大值，问如何划分才能使最大的s最小？

这就是“最大值(所有子序列和的最大值)最小化”。

例如序列{2, 2, 3, 4, 5, 1}，将其划分成k=3个连续的子序列。下面举两种分法： {(2, 2, 3),(4, 5),(1)}，子序列和分别是7、9、1，最大值是9； {(2, 2, 3),(4),(5,1)}，子序列和是7、4、6，最大值是7。第2种分法比第1种分法好。

仍然用猜的方法。在一次划分中猜一个x，对任意的Si都有Si≤x，也就是说x是所有Si中的最大值。

如何找到这个x？简单的办法是枚举每一个x，用贪心法每次从左向右尽量多划分元素，Si不能超过x，划分的子序列的个数为k个，但是枚举所有的x太耗时了。

用二分法可以加速猜x的过程。用二分法在［max, sum］范围内查找满足条件的x，其中max是序列中最大元素的值，sum是所有元素的和。

5.4.2例题

二分法的题目非常多，请读者大量练习二分法的题目。下面举几个例子。






 例5．8
求阶乘lanqiaoOJ 2145


问题描述： 满足n!的末尾恰好有k个0的最小的n是多少？如果这样的n不存在，输出-1。 

输入： 输入一个整数k。 

输出： 输出一个整数，表示答案。

输入样例：  

2输出样例： 

10

评测用例规模与约定： 对于30%的评测用例，1≤k≤106； 对于100%的评测用例，1≤k≤1018。


尾零是由2×5相乘得到的，所以只需要计算n!中2和5的因子数量。又因为n!中2的因子数量远大于5的因子数量，所以只需要计算5的因子数量。

例如25!=25×…×20×…×15×…×10×…×5×…，其中的25、20、15、10、5分别有2、1、1、1、1共6个因子5，所以尾零有6个。

(1) 通过30%的测试。

简单的方法是检查每个n，计算n!的尾零数量，尾零数量等于k的n就是答案。下面代码中第3行的while循环n/5次，对于100%的数据，1≤k≤1018，由于n比k还大，代码超时。

check(n)函数返回n!的尾零数量，也就是计算n!有多少个因子5，读者可以按自己的思路实现这个函数。下面的check()用了巧妙的方法。以25!为例，对5有贡献的是5、10、15、20、25，即5×1、5×2、5×3、5×4、5×5，共有6个5，其中5个5是由25/5得到的，即5×i中的5； 还有一个5是循环5次后多的一个5，即i×5的5。再例如100!，尾零的数量包括两部分： 100/5=20、20/5=4。




1def check(n):
2cnt = 0
3while n:
4cnt += n // 5
5n //= 5
6return cnt
7k = int(input())
8for n in range(5, 10**18, 5):
9cnt = check(n)
10if cnt == k:
11print(n)
12break
13if cnt >k:
14print(-1)
15break




(2) 通过100%的测试。

本题可以用二分优化，也就是用二分来猜n。因为n递增时，尾零的数量也是单调递增的，符合二分法的应用条件。

下面讨论代码的计算复杂度。第11行的二分是O(log2E)，这里E=1019。第1行做一次check()差不多是O(1)。总计算量约为log2E=log21019<70次。




1def check(n):# 计算n!的末尾有多少个0
2cnt = 0
3while n:
4cnt += n // 5
5n //= 5
6return cnt
7k = int(input())
8L = 0
9R = 10**19                # R的初值为一个极大的数
10while L < R:
11mid = (L + R) // 2
12if check(mid) >= k:R = mid  # mid!的尾零数量超过了k，说明mid大了
13else:L = mid + 1      # mid小了
14if check(R) == k:print(R)
15else:print(-1)









 例5．9
2022年第十三届蓝桥杯省赛Python大学C组试题I： 青蛙过河 lanqiaoOJ 2097


时间限制： 1s 内存限制： 512MB 本题总分： 25分

问题描述： 小青蛙住在一条河的河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降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是否合法。




1def check(sum, mid, x):
2for i in range(1, len(sum) - mid + 1):# 每个区间的高度之和都要大于或等于2x
3if sum［i + mid - 1］ - sum［i - 1］ < 2 * x:
4return False
5return True
6n, x = map(int, input().split())
7h = ［0］ * n
8h［1:］ = list(map(int, input().split()))  # h［0］不用，从h［1］开始
9sum = ［0］ * n
10sum［0］ = 0
11for i in range(1, n):
12sum［i］ = sum［i - 1］ + h［i］      # 跳跃区间的高度之和
13L, R = 1, n
14while L < R:
15mid = (L + R) // 2
16if check(sum, mid, x):R = mid
17else:L = mid + 1
18print(L)









 例5．10
2023年第十四届蓝桥杯省赛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<Li。


按题目的设定，管道内是贯通的，每个阀门都连着一个进水管，打开阀门后会有水从这个进水管进入管道，并逐渐流到管道内的所有地方。

先解释样例。设长度L的单位是米，水流的速度是米/秒。L=1处的阀门在第S=1秒打开，T=5秒时，覆盖范围L－(T－S)=1-(5-1)=-3，L＋(T－S)=1+(5-1)=5； L=6处的阀门在S=5秒打开，T=5秒时，只覆盖了L=6； L=10处的阀门在L=2秒打开，T=5秒时，覆盖范围L－(T－S)=10-(5-2)=7，L＋(T－S)=10+(5-2)=13。所以这3个阀门在T=5时覆盖了［-3, 5］、6、［7，13］，管道中的所有传感器都检测到了水流。

读者可能会立刻想到可以用二分法猜时间T。先猜一个T，然后判断在T时刻是否整个管道有水。如何判断？位于Li的阀门，它影响到的小区间是［Li－(Ti－Si), Li＋(Ti－Si)］，n个阀门对应了n个小区间。那么问题转化为： 给出n个小区间，是否能覆盖整个大区间。这是贪心法中的“区间覆盖问题”，请大家阅读5.5节中对“区间覆盖问题”的说明。

本题还可以再简单一点。题目给的评测用例指出Li-1<Li，即已经按左端点排序，可以省去排序的步骤。

在check(t)函数中，定义last_L为当前覆盖到的最左端，last_R为最右端。然后逐个遍历所有的小区间，看它对扩展last_L、last_R有无贡献。在所有小区间处理完毕后，如果［last_L，last_R］能覆盖整个［1, len］区间，则这个时刻t就是可行的。




1def check(t):# 检查t时刻，管道内是否都有水
2cnt = 0
3last_L = 2
4last_R = 1
5for i in range(n):
6if t >=S［i］:
7cnt += 1   # 特判t是否够大
8left = L［i］ - (t - S［i］)
9right = L［i］ + (t - S［i］)
10if left < last_L:
11last_L = left
12last_R = max(last_R, right)
13elif left <=last_R + 1:
14last_R = max(last_R, right)
15if cnt == 0:return False
16if last_L <=1 and last_R >=length:
17return True
18else: return False
19 
20n, length = map(int, input().split())
21L = ［］
22S = ［］
23for _ in range(n):
24l, s = map(int, input().split())
25L.append(l)
26S.append(s)
27LL,R = 0, int(2e9)         # LL避免和L［］重名
28ans = -1
29while LL <=R:            # 二分
30mid = (R + LL) >>1     
31if check(mid):
32ans = mid
33R = mid - 1
34else:LL = mid + 1 
35print(ans)



下面是一道思维有难度的二分法题目。






 例5．11
2022年第十三届蓝桥杯省赛Python大学B组试题H： 技能升级 lanqiaoOJ 2129


时间限制： 1s 内存限制： 512MB 本题总分： 20分

问题描述： 小蓝最近正在玩一款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次，每次升级时选用攻击力最高的技能，然后更新它的攻击力。

下面代码的复杂度是多少？第12行升级m次，是O(m)的； 第13行选用最大攻击，使用Python的max()函数，是O(n)的。总复杂度为O(mn)，只能通过40%的测试。




1import math
2n,m = map(int,input().split())
3a = ［］# 存ai
4b = ［］                               # 存bi
5c = ［］                               # ai/bi
6for i in range(n):
7a_,b_ = map(int,input().split())
8a.append(a_)
9b.append(b_)    
10c.append(math.ceil(a_/b_))       # 向上取整
11ans = 0
12for i in range(m):                   # 一共升级m次
13max_num = max(a)                 # 每次升级时使用最大的攻击
14index = a.index(max_num)        # 最大攻击对应的序号    
15a［index］ -= b［index］             # 更新攻击力
16if c［index］>0: ans += max_num    # 累加攻击力
17c［index］ -= 1
18print(ans)




(2) 暴力法+优先队列。

上面的代码可以稍做改进。在n个技能中选用最高攻击力，可以使用优先队列，一次操作的复杂度为O(log2n)。m次升级，总复杂度为O(mlog2n)，能通过60%的测试。

下面是Python的“暴力法+优先队列”实现。优先队列用堆实现，heapq默认是小根堆，第7行把a取负，将最大值变成了最小值。




1from heapq import *
2n,m = map(int,input().split()) 
3q = ［］ 
4ans = 0 
5for i in range(n):
6a,b = map(int,input().split())
7heappush(q,(-a,b)) 
8for i in range(m):# 升级m次
9p = heappop(q)   # 每次升级时使用最大的攻击。读队列最大值并删除
10a,b = -p［0］,p［1］
11ans += a                        # 累加攻击力
12a = max(a - b, 0)               # 更新攻击力
13if a != 0: heappush(q,(-a,b))   # 重新放进队列
14print(ans)



(3) 二分法。

本题的正解是二分法，能通过100%的测试。

本题m≤2×109太大，若逐一升级m次必定会超时。但是不能直接对m进行二分，因为需要知道每个技能升级多少次，而这与m无关。

思考升级技能的过程，是每次找攻击力最高的技能。对某个技能，最后一次升级的攻击力肯定比之前升级的攻击力小，也就是前面的升级都更大。可以设最后一次升级提升的攻击力是mid，对每个技能，若它最后一次能升级mid，那么它前面的升级都更大。所有这样最后能达到mid的技能，它们前面的升级都应该使用。用二分法找到这个mid，另外，升级技能减少的攻击力的过程是一个等差数列，用O(1)次计算即可知道每个技能升级了几次。知道了每个技能升级的次数，就可以计算一共提升了多少攻击力，这就是题目的答案。

下面给出Python代码。check(mid)函数找这个mid。第6行，若所有技能升级的总次数大于或等于m次，说明mid设小了，在第16行让L增大，即增加了mid。第8行，若所有技能升级的总次数小于m次，说明mid设大了，在第17行让R减小，即缩小了mid。

分析代码的复杂度。第14~17行，二分O(log2A)次，这里A表示1≤Ai≤106； 每次check()是O(n)，二分的总复杂度是O(nlog2A)。第20行的for循环是O(n)。代码的总复杂度是O(nlog2A)+O(n)，能通过100%的测试。




1def check(mid):# 最后一次技能升级，最多能不能到mid
2cnt = 0 
3for a,b in skills:    
4if a < mid:continue  # 第i个技能的初值还不够mid，不用这个技能
5cnt += (a - mid) // b + 1  # 第i个技能用掉的次数
6if cnt >=m:   # 所有技能升级的总次数大于或等于m次，说明mid设小了
7return True  
8return False            # 所有技能升级的总次数小于m次，说明mid设大了
9 
10n, m = map(int, input().split())
11skills = ［list(map(int, input().split())) for _ in range(n)］
12
13L,R = 1,1000000                # 二分枚举最后一次攻击力最大能加多少
14while(L <=R):   
15mid = (L + R) // 2
16if check(mid): L = mid + 1           # 增加mid
17else:R = mid - 1           # 减小mid
18attack = 0
19cnt = m
20for a,b in skills:  
21if a < R:continue
22t = (a - L) // b + 1               # 第i个技能升级的次数
23if a - b * (t - 1) == R:
24t -= 1             # 这个技能每次升级刚好等于R，其他技能更好
25attack += (a * 2 - (t - 1) * b) * t / 2  
26cnt -= t
27print(int(attack) + cnt * R)



【练习题】

二分的题目非常多，每个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元； 最后选面值最小的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






按单位价格排序，最贵的先拿，便宜的后拿。




1n, c = map(int, input().split())
2a = ［］
3for i in range(n):
4w, v = map(int, input().split())
5p = v / w
6a.append((w, v, p))
7a.sort(key=lambda x: x［2］, reverse=True)
8sum = 0.0
9for i in range(n):
10if c >= a［i］［0］:
11c -= a［i］［0］
12sum += a［i］［1］
13else:
14sum += c * a［i］［2］
15break
16print("%.2f" %sum)



2. 不相交区间问题

不相交区间问题或者称为区间调度问题、活动安排问题。

给定一些区间(活动)，每个区间有左端点和右端点(开始时间和终止时间)，要求找到最多的不相交区间(活动)。

以下按“活动安排问题”来解释。

这个问题的目的是求最多活动数量，所以持续时间长的活动不受欢迎，受欢迎的是尽快结束的、持续时间短的活动。

考虑以下3种贪心策略： 

(1) 最早开始时间。先选最早开始的活动a，当a结束后，再选下一个最早开始的活动。这种策略不好，因为它没有考虑活动的持续时间。假如a一直不结束，那么其他活动就不能开始。

(2) 最早结束时间。先选最早结束的活动a，a结束后，再选下一个最早结束的活动。这种策略是合理的。越早结束的活动，越能腾出后续时间容纳更多的活动。



图5.7活动安排


(3) 用时最少。先选时间最短的活动a，再选不冲突的下一个最短活动。这个策略似乎也可行，但是很容易找到反例，证明这个策略不正确。

如图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<Ri)，表示比赛开始、结束的时间。其中，1≤n≤106，1≤Li<Ri≤106。

输出： 输出一个整数，表示最多参加的比赛数目。

输入样例： 

3

0 2

2 4

1 3
输出样例： 

2





按策略(2)编码。




1n = int(input())
2a = ［］
3for _ in range(n):
4L, R = map(int, input().split())
5a.append((L, R))
6a.sort(key=lambda x: x［1］)# 按照结束时间排序。请与下一个例题代码比较
7ans = 0
8lastend = -1
9for i in range(n):
10if a［i］［0］ >=lastend:
11ans += 1
12lastend = a［i］［1］
13print(ans)



3. 区间合并问题

给定若干个区间，合并所有重叠的区间，并返回不重叠的区间的个数。

以图5.8为例，1、2、3、5合并，4、6合并，新区间是1′、4′。




图5.8区间合并


贪心策略： 按区间的左端点排序，然后逐一枚举每个区间，合并相交的区间。

定义不重叠的区间的个数(答案)为ans。设当前正在合并的区间的最右端点为end，当枚举到第i个区间［Li, Ri］时： 

若Li≤end，说明与第i个区间相交，需要合并，ans不变，更新end=max(end, Ri)。

若Li>end，说明与第i个区间不相交，ans加1，更新end=max(end, Ri)。

请读者用图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<Ri)。其中，1≤n≤105，1≤Li<Ri≤1017。

输出： 输出共一行，包含一个正整数，为覆盖后的区间总长。

输入样例： 

3

1 100000

200001 1000000

100000000 100000001
输出样例： 

900002






按上述贪心策略写出代码。




1class Data:          
2def __init__(self, L, R):
3self.L = L
4self.R = R
5
6n = int(input())
7a = ［］
8for _ in range(n):
9
10L, R = map(int, input().split())
11a.append(Data(L, R))
12a.sort(key=lambda x: x.L)
13lastend = -1
14ans = 0
15for i in range(n):
16if a［i］.R >=lastend:
17ans += a［i］.R - max(lastend, a［i］.L) + 1
18lastend = a［i］.R + 1
19print(ans)



5.5.2例题

贪心题在算法竞赛中也是必考点，由于贪心法可以灵活地嵌入题目当中与其他算法结合，题目可难、可易。






 例5．15
2023年第十四届蓝桥杯省赛Python大学C组试题E： 填充lanqiaoOJ 3519


时间限制： 10s 内存限制： 512MB 本题总分： 15分

问题描述： 有一个长度为n的01串s，其中有一些位置标记为“?”，在这些位置上可以任意填充0或者1。请问如何填充这些位置可以使这个01串中出现的互不重叠的00和11子串最多，输出子串的个数。

输入： 输入一行，包含一个字符串。

输出： 输出一行，包含一个整数，表示答案。

输入样例： 

1110?0
输出样例： 

2

样例说明： 如果在问号处填0，则最多出现一个00和一个11，即111000。
对于所有评测用例，1≤n≤1000000。


本题有贪心、DP两种解法。DP解法见第8章，这里用贪心求解。

题目要求00、11尽可能多，所以目的是尽可能多配对，配对只在相邻s［i］和s［i+1］之间发生。从s［0］、s［1］开始，每次观察相邻的两个字符s［i］、s［i+1］，讨论以下情况。

(1) s［i］=s［i+1］，这两个字符可能是“00”“11”“??”，都配对。下一次观察s［i+2］、s［i+3］。

(2) s［i］或s［i+1］有一个是“?”，那么可以匹配。例如“1?”“?1”“0?”“?0”，都是匹配的。下一次观察s［i+2］、s［i+3］。

(3) s［i］='0'，s［i+1］='1'，不配对。下一次观察s［i+1］、s［i+2］。

(4) s［i］='1'，s［i+1］='0'，不配对。下一次观察s［i+1］、s［i+2］。

下面是代码，只需要计算(1)、(2)即可。在代码中只有一个while循环，计算复杂度为O(n)。




1s = input()
2ans = 0
3i = 0
4while i < len(s) - 1:
5if s［i］ == s［i+1］:
6ans += 1
7i += 2
8elif s［i］ == '?' or s［i+1］ == '?':
9ans += 1
10i += 2
11else: i += 1
12print(ans)









 例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的商品，由于价格已经排序，可以用二分法加快查找的时间。Python有一个自带的二分函数bisect_left()，请读者自行了解bisect_left()函数并熟悉它的应用。




1import bisect
2n = int(input())
3a = list(map(int, input().split()))
4a.sort()
5ans = 0
6cnt = 0
7last = -1# 购买的两件商品中便宜的那一件
8last_id = n - 1                # 能免单的位置
9vis = ［False］ * n              # vis［i］=True表示已经免单了
10for i in range(n - 1, -1, -1):
11if not vis［i］:
12cnt += 1
13ans += a［i］            # last是买的第2件
14last = a［i］
15if cnt == 2:               # 买了两件
16cnt = 0
17x = bisect.bisect_left(a, last // 2, 0, last_id)
18# 用二分找能免单的商品a［x］
19if x >last_id or a［x］ >last // 2:x -= 1   # 向下取整
20if x >=0:
21vis［x］ = True        # x免单了
22last_id = x - 1      # 后面能免单的区间范围是［0,last_id］
23print(ans)









 例5．17
购物https://www.luogu.com.cn/problem/P1658


问题描述： 某人要去购物，现在手上有n种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量少的硬币，但要能组合出1到x之间的任意值。 

输入： 第一行两个数x、n，第二行n个数，表示每种硬币的面值。 

输出： 输出最少需要携带的硬币的个数，如果无解，输出-1。 

评测用例规模与约定： 对于30%的评测用例，n≤3，x≤20； 对于100%的评测用例，n≤10，x≤103。

输入样例：  

20 4

1 2 5 10
输出样例： 

5




为了方便处理，把硬币的面值从小到大排序。

无解是什么情况？如果没有面值为1的硬币，组合不到1，无解。如果有面值为1的硬币，那么所有的x都能满足，有解。所以，无解的充要条件是没有面值为1的硬币。

组合出1~x的任意值需要的硬币多吗？学过二进制的人都知道，1、2、4、8、……、2n-1这n个值可以组合出1~2n-1的所有数。这说明只需要很少的硬币就能组合出很大的x。

设已经组合出1~s的面值，即已经得到数字1、2、3、……、s，下一步扩展到s+1。当然，如果能顺便扩展到s+2、s+3、……扩展得越大越好，这样就能用尽量少的硬币扩展出更大的面值。

如何扩展到s+1？就是在数字1、2、3、……、s的基础上添加一个面值为v的硬币，得到s+1。v可以选1、2、……、s+1，例如v=1，s+1=s+v； v=2，s+1=s-1+v； ……； v=s+1，s+1=v。如果v=s+2，就不能组合到s+1了。

v的取值范围是［1, s+1］，为了最大扩展，选v为［1, s+1］内的最大硬币，此时s扩展到s+v。这就是贪心策略。

以本题的输入样例为例说明计算过程。设答案为ans。

先选硬币1，得到s=1。ans=1。

再选［1, s+1］=［1, 2］内的最大硬币2，扩展s=1为s=1+v=3。ans=2。

再选［1, s+1］=［1, 4］内的最大硬币2，得到s=5。ans=3。

再选［1, s+1］=［1, 6］内的最大硬币5，得到s=10。ans=4。

再选［1, s+1］=［1, 11］内的最大硬币10，得到s=20。ans=5。此时s≥x，结束。

所以仅需要5个面值为1、2、2、5、10的硬币就可以组合得到1、2、3、4、……、20。




1x, n = map(int, input().split())
2a = list(map(int, input().split()))
3a.sort()
4if a［0］ != 1:  print(-1); exit()
5s, ans = 0, 0
6while s < x:
7for v in range(n - 1, -1, -1):
8if a［v］ <=s + 1:
9s += a［v］
10ans += 1
11break
12print(ans)










 例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)。




1n = int(input())
2a = ［］
3for i in range(n):
4x, w = map(int, input().split())
5a.append({'l': x-w, 'r': x+w})
6a.sort(key=lambda x: x［'r'］)# 按右端点排序
7R, ans = a［0］［'r'］, 1
8for i in range(1, n):      # 选剩下活动中最早结束的活动，跳过冲突的活动
9if a［i］［'l'］ >= R:
10R = a［i］［'r'］
11ans += 1
12print(ans)









 例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+cj<tot+cj+ pi，
即pj-cj<pi-ci，设Δ=p-c, 有Δj<Δi, Δ是原价和优惠价的差额。

也就是说，只要在使用优惠券的衣服中存在一个j有Δj<Δi，即第j件的优惠幅度不如第i件的优惠幅度，那么把j的优惠券转给i会有更好的结果。

但是上述讨论还是有问题，它可能导致超过总花费。例如： 

衣服： a,b,c

优惠价： 20, 40, 42

原价： 30, 80, 49

m=69元，k=1张优惠券。先用优惠券买a； 下一步发现Δa<Δb，把优惠券转移给b，现在的花费是30+40=70，超过m了。最优解是a仍然用优惠价，c用原价。所以简单地计算候选衣服i的差额Δi=pi-ci，然后与Δj比较并不行。

那么如何在候选衣服中选一件才能最优惠呢？

(1) 用原价买，那么应该是这些衣服中的最低原价。

(2) 用优惠价买，那么应该是这些衣服中的最低优惠价。

所以在候选衣服中的最低原价和最低优惠价之间计算差额，并与Δj比较才是有意义的。

在编码时，用3个优先队列处理3个关键数据： 

(1) 已使用优惠券的衣服的优惠幅度Δ。在已经使用优惠券的衣服中，谁应该拿出来转移优惠券？应该是那个优惠幅度Δ最小的，这样转移之后才能获得更大优惠。用优先队列d找最小的Δ。

(2) 没使用优惠券的衣服的原价。用一个优先队列p找最便宜的原价。

(3) 没使用优惠券的衣服的优惠价。用一个优先队列c找最便宜的优惠价。

在代码中这样处理优惠券： 

(1) 先用完k个优惠券，从c中连续取出k个最便宜的即可。

(2) 优惠券替换。从p中取出原价最便宜的p1，从c中取出优惠价最便宜的c2，然后从d中取出优惠幅度最小的d： 

① 若d>p1-c2，说明替换优惠券不值得，不用替换。下一件衣服用原价p1买。

② 若d≤p1-c2，说明替换优惠券值得，下一件衣服用优惠价c2买，原来用优惠券的改成用原价。

本题总体上是贪心，用3个优先队列处理贪心，但是优惠券的替换操作是贪心的“反悔”，所以称为“反悔贪心”。贪心是连续做局部最优操作，但是有时局部最优推不出全局最优，此时可以用反悔贪心，撤销之前做出的决策，换条路重新贪心。




1import heapq
2n, k, m = map(int, input().split())
3p = ［0］ * (n+1)
4c = ［0］ * (n+1)
5buy = ［False］ * (n+1)# buy［i］=1： 第i个物品被买了
6P = ［］
7C = ［］
8D = ［］
9for i in range(1, n+1):
10p［i］, c［i］ = map(int, input().split())
11heapq.heappush(P, (p［i］, i))
12# 原价，还没买的在这里，如果买了就弹出去
13heapq.heappush(C, (c［i］, i))
14# 优惠价，还没买的在这里，如果买了就弹出去
15for i in range(1, k+1):
16heapq.heappush(D, 0)            # k张优惠券，开始时每个的优惠为0
17ans = 0
18while P and C:
19p1 = P［0］                       # 取出原价最便宜的
20c2 = C［0］                       # 取出优惠价最便宜的
21if buy［p1［1］］:                  # 这个已经买了，跳过
22heapq.heappop(P); continue   
23if buy［c2［1］］:                  # 这个已经买了，跳过
24heapq.heappop(C); continue   
25if D［0］ >p1［0］-c2［0］:          # 用原价买i更划算，不用替换优惠券
26m -= p1［0］                  # 买原价最便宜的
27heapq.heappop(P)      # 这里不要C.pop()，因为买的是p1，不是c2
28buy［p1［1］］ = True           # 标记p1买了
29else:                           # 替换优惠券。前k个都先执行这里
30m -= c2［0］+D［0］             # 买优惠价最便宜的
31heapq.heappop(C)       # 这里不要p.pop()，因为买的是c2，不是p1
32buy［c2［1］］ = True           # 标记c2买了
33heapq.heappop(D)            # 原来用优惠券的退回优惠券
34heapq.heappush(D, p［c2［1］］-c［c2［1］］)
35# c2使用优惠券，重新计算delta并进队列
36if m >=0:ans += 1
37else:break
38print(ans)



【练习题】

lanqiaoOJ： 三国游戏3518、平均3532、答疑1025、身份证3849、找零钱3854、01搬砖2201、卡牌游戏1057、寻找和谐音符3975、小蓝的旅行计划3534、翻硬币209、防御力226。

洛谷： 排座椅P1056、母舰P2813、排队接水P1223、小A的糖果P3817、加工生产调度P1248、负载平衡问题P4016。




5.6扩 展 学 习
从本章开始进入了算法学习阶段。本章的“基本算法”是一些“通用”的算法，可以在很多场景下应用。

本书2.1节中曾提到计算思维的作用，通过做杂题可以帮助大家建立基本的、自发的计算思维。在计算机科学中有大量经典的算法和数据结构，它们代表了计算机科学中最璀璨的花朵。在这些知识点中基本算法易于理解、适用面广、精巧高效，是计算思维的奠基，真正的计算思维从这里开始。

除了本章介绍的前缀和、差分、二分、贪心，基本算法还有尺取法、倍增法、离散化、分治等。在逐渐深入学习算法的过程中，这些基本算法都是必须掌握的知识点。