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


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




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

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

5．1．1算法的概念

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

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

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

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

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

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

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

5．1．2计算资源

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

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

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

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

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

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

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




1import java.util.Date;
2public class Main {
3public static void main(String［］ args) {
4int k = 0, n = 100000000;//1亿
5long s = new Date().getTime(); //开始时间
6while (n-- > 0)    k += 5;   
7long t = new Date().getTime();//终止时间
8System.out.println((double) (t - s) / 1000);
9}
10}



在作者的笔记本计算机上运行，循环n=1千万次，用时0．069s。换了一个台式计算机，用时0．03s。Java的循环比C++的循环更快。一般认为Java比C++慢，这里Java可能做了优化。

竞赛评测用的判题服务器(OJ系统)，性能可能比这个好一些，也可能差不多。对于C++题目，如果题目要求“时间限制: 1s”，那么内部的循环次数n应该在1亿次以内，Java也在1亿次以内。对于同等规模的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=1千万时，log2n<24。

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

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

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

下面是Java代码，注意sum［］需要用long long类型。

代码的计算复杂度，第10行sort()是O(nlog2n)，第12、14行的for循环都是O(n)，总复杂度为O(nlog2n)。




1import java.util.Arrays;
2import java.util.Scanner;
3public class Main {
4public static void main(String［］ args) {
5Scanner sc = new Scanner(System.in);
6int n = sc.nextInt();
7int k = sc.nextInt();
8long［］ a = new long［n+1］;
9for (int i = 1; i <= n; i++) a［i］ = sc.nextLong();
10Arrays.sort(a, 1, n+1);
11long［］ sum = new long［n+1］;
12for (int i = 1; i <= n; i++) sum［i］ = sum［i-1］ + a［i］;
13long ans = (long)1e18;
14for (int p = 1; p <= k; p++)
15ans = Math.min(sum［n］ - sum［n+p-k］ + sum［2*p］, ans);
16System.out.println(ans);
17}
18}



再看一道简单题。







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




1import java.util.Scanner;
2public class Main{
3public static void main(String［］ args) {
4int N = (int)(1e5+10);
5long sum［］ = new long［N］;  //前缀和
6Scanner sc = new Scanner(System.in);
7int n = sc.nextInt();
8for(int i=1;i<=n;i++) {
9int a = sc.nextInt();
10sum［i］ = sum［i-1］ + a;  //求前缀和
11}
12long ans = sum［n］;
13for(int i=1;i<=n;i++)    //较大的和的最小值是多少
14ans = Math.min(ans, Math.max(sum［i］, sum［n］-sum［i］));  
15System.out.println(ans);
16}
17}



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







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

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




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int n = sc.nextInt();
6int［］ a = new int［n］;
7for (int i = 0; i < n; i++)   a［i］ = sc.nextInt();
8long ans = 0;    //注意这里用long
9for (int L = 0; L < n; L++) {//遍历所有子段［L,R］
10for (int R = L; R < n; R++) {
11int sum = 0;
12for (int i = L; i <= R; i++) sum ^= a［i］;//子段和
13ans += sum;//累加所有子段和
14}
15}
16System.out.println(ans);
17}
18}



(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］，下面代码的第11行用这个公式的简化形式求解了前缀和。

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




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int n = sc.nextInt();
6int［］ a = new int［n］;
7for (int i = 0; i < n; i++)   a［i］ = sc.nextInt();
8long ans = 0;
9for (int L = 0; L < n; L++) {
10long sum = 0;     //sum是包含a［L］的子段的前缀和
11for (int R = L; R < n; R++) {
12sum ^= a［R］;  //用递推求前缀和sum
13ans += sum;   //累加所有子段和
14}
15}
16System.out.println(ans);
17}
18}



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




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int n = sc.nextInt();
6int［］ a = new int［n］;
7for (int i = 0; i < n; i++)  a［i］ = sc.nextInt();  
8long ans = 0;
9for (int k = 0; k <= 20; k++) {  //所有a不超过20位
10int zero = 1, one = 0;     //统计第k位的0和1的数量
11long cnt = 0, sum = 0;//cnt用于统计第k位有多少对si⊕sj =1
12for (int i = 0; i < n; i++) {
13int v = (a［i］ >> k) & 1;//取a［i］的第k位
14sum^= v;
15//对所有a［i］的第k位做异或得到sum，sum等于0或1
16if (sum == 0) {    //前缀和为0
17zero++;  //0的数量加1
18cnt += one;
19//这次sum=0，这个sum与前面等于1的sum异或得1
20} else {     //前缀异或为1
21one++;   //1的数量加1
22cnt += zero;
23//这次sum=1，这个sum与前面等于0的sum异或得1
24}
25}
26ans += cnt * (1L << k); //第k位的异或和相加
27}
28System.out.println(ans);
29}
30}



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







 例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(n×m×c2)，能通过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］


图5．2二维数组和二维平面

把a［i］［j］的(i,j)看成二维平面的坐标，那么sum［i］［j］就是左下角坐标(1,1)和右上角坐标(i,j)围成的矩形中所有坐标点的和，如图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］被加了两次，所以要减去一次。

下面Java代码的第12行让sum［］［］和a［］［］共用，从而节省一半空间。如果分别定义sum［］［］和a［］［］，会超过题目的空间限制。




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int n = sc.nextInt();
6int m = sc.nextInt();
7int c = sc.nextInt();
8int［］［］ a = new int［n + 1］［m + 1］;
9for (int i = 1; i <= n; i++) {
10for (int j = 1; j <= m; j++) {
11a［i］［j］ = sc.nextInt();
12a［i］［j］ = a［i-1］［j］ + a［i］［j-1］ - a［i-1］［j-1］ + a［i］［j］;
13//上一行等同于：s［i］［j］ = s［i-1］［j］ + s［i］［j-1］ - s［i-1］［j-1］ + a［i］［j］;
14}
15}
16int Max = Integer.MIN_VALUE;
17int x = 0;
18int y = 0;
19for (int x1 = 1; x1 <= n - c + 1; x1++) {
20for (int y1 = 1; y1 <= m - c + 1; y1++) {//枚举所有坐标点
21int x2 = x1 + c - 1;
22int y2 = y1 + c - 1;  //正方形的右下角坐标
23int ans=a［x2］［y2］-a［x2］［y1-1］-a［x1-1］［y2］+a［x1-1］［y1-1］;
24if (ans > Max) {
25Max = ans;
26x = x1;
27y = y1;
28}
29}
30}
31System.out.println(x + " " + y);
32}
33}






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［］。将这些小线段相加，就得到了从起点开始的长线段a［］，如图5.3所示。



图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%的测试。

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

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

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

注意，如果把下面第12行中的long改成int，那么只能通过30%的测试。




1import java.util.Arrays;
2import java.util.Scanner;
3public class Main {
4public static void main(String［］ args) {
5Scanner sc = new Scanner(System.in);
6int N = 100003;
7int［］ a = new int［N］;    //a［］:读入数组 
8int［］ cnt = new int［N］;  //cnt［i］：第i个数被加的次数
9int n = sc.nextInt();
10for (int i = 1; i <= n; i++)  a［i］ = sc.nextInt();  
11int m = sc.nextInt();
12long ans1 = 0, ans2 = 0; //ans1: 原区间和； ans2: 新区间和
13while (m-- > 0) {
14int L = sc.nextInt();
15int R = sc.nextInt();
16for (int i = L; i <= R; i++) 
17cnt［i］++;   //第i个数被加了一次，累计一共加了多少次
18}
19for (int i = 1; i <= n; i++) 
20ans1 += (long) a［i］ * cnt［i］; //在原数组上求区间和
21Arrays.sort(a, 1, n + 1);
22Arrays.sort(cnt, 1, n + 1);
23for (int i = 1; i <= n; i++)
24ans2 += (long) a［i］ * cnt［i］;  
25System.out.println(ans2 - ans1);
26}
27}



(2) 通过100%的测试。

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

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

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

代码的计算复杂度，14行的while循环只有O(m)，最耗时的是第24、25行的排序，复杂度为O(nlog2n)，能通过100%的测试。




1import java.util.*;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int N = 100003;
6int［］ a = new int［N］;
7int［］ d = new int［N］;
8int［］ cnt = new int［N］;  
9int n = sc.nextInt();
10for (int i = 1; i <= n; i++)  
11a［i］ = sc.nextInt();  
12int m = sc.nextInt();
13long ans1 = 0, ans2 = 0;
14while (m-- > 0) {
15int L = sc.nextInt();
16int R = sc.nextInt();
17d［L］++;   d［R+1］--;
18}  
19cnt［0］ = d［0］;
20for (int i = 1; i <= n; i++) 
21cnt［i］ = cnt［i-1］ + d［i］; //用差分数组d［］求cnt［］
22for (int i = 1; i <= n; i++) 
23ans1 += (long) a［i］ * cnt［i］;  
24Arrays.sort(a, 1, n+1);
25Arrays.sort(cnt, 1, n+1);  
26for (int i = 1; i <=n; i++)  
27ans2 += (long) a［i］ * cnt［i］;  
28System.out.println(ans2 - ans1);  
29}
30}



再看一道例题。







 例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<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) 用差分处理输入。下面代码中的第10行读一个列的起点位置li和终点位置hi，代码第11行和第12行输入d［］，d［］是a［］的差分。计算量仅为O(N)。

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

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




1import java.util.*;
2import java.io.*;
3public class Main{
4static int N = 1000010;
5static long［］ d = new long［N］, a = new long［N］, sum = new long［N］;
6public static void main(String［］ args) throws Exception{
7Scanner scan = new Scanner(System.in);
8int n = scan.nextInt(), h = scan.nextInt();
9for(int i = 1; i <= n; i++) {
10int li = scan.nextInt(), hi = scan.nextInt();
11d［li］++;   //可替换为  sum［li］++;
12d［hi+1］--; //可替换为  sum［hi+1］--;
13}
14for(int i = 1; i <= n; i++)//用差分数组计算原数组
15a［i］ = a［i-1］ + d［i-1］;//可替换为  sum［i］ += sum［i-1］;
16for(int i = 1; i <= n; i++)//用原数组计算前缀和数组
17sum［i］ = sum［i-1］ + a［i］;//可替换为  sum［i］ += sum［i-1］;
18long ans = sum［h-1］;
19for(int left = 1; left+h-1 <=n; left++)
20ans = Math.max(ans, sum［left+h-1］ - sum［left-1］);
21System.out.println((long)n * h - ans);
22}
23}



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］
这个公式可以通过图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二维差分的区间修改


读者可以用图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) 模拟。

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




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int［］［］ a = new int［2100］［2100］;
6int n = sc.nextInt();
7int m = sc.nextInt();
8for (int i = 0; i < m; i++) {
9int x1 = sc.nextInt();
10int y1 = sc.nextInt();
11int x2 = sc.nextInt();
12int y2 = sc.nextInt();
13for (int j = x1; j <= x2; j++) 
14for (int k = y1; k <= y2; k++) 
15a［j］［k］ ^= 1; 
16}
17for (int i = 1; i <= n; i++) {
18for (int j = 1; j <= n; j++) 
19System.out.print(a［i］［j］);  
20System.out.println();
21}
22}
23}



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

这是一道很直白的二维差分题。第7~10行是二维差分计算，其实改成注释中的写法也可以，请大家思考。




1import java.util.Scanner;
2public class Main {
3static int［］［］ a;
4static int［］［］ d;
5static int n, m;
6public static void insert(int x1, int y1, int x2, int y2) {
7d［x1］［y1］++;  //d［x1］［y1］  ^=1;
8d［x1］［y2+1］--;//d［x1］［y2+1］ ^=1;
9d［x2+1］［y1］--;//d［x2+1］［y1］ ^=1;
10d［x2+1］［y2+1］++;//d［x2+1］［y2+1］ ^=1;
11}
12public static void main(String［］ args) {
13Scanner sc = new Scanner(System.in);
14n = sc.nextInt();
15m = sc.nextInt();
16a = new int［n + 2］［n + 2］;
17d = new int［n + 2］［n + 2］;
18for (int i = 0; i < m; i++) {
19int x1 = sc.nextInt();
20int y1 = sc.nextInt();
21int x2 = sc.nextInt();
22int y2 = sc.nextInt();
23insert(x1, y1, x2, y2);
24}
25for (int i = 1; i <= n; i++) {
26for (int j = 1; j <= n; j++) {
27a［i］［j］ = d［i］［j］ + a［i-1］［j］ + a［i］［j-1］ - a［i-1］［j-1］;
28System.out.print(a［i］［j］ & 1);
29}
30System.out.println();
31}
32}
33}



【练习题】

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
2int mid = (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
5}



答案在［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为止，即找到了答案所处的位置。




1import java.util.*;
2class Main {
3static int［］ a = new int［105］;
4static boolean check(int x, int mid) { return x <= a［mid］; }
5static int bin_search(int n, int x) {
6int L = 1;
7int R = n;
8while (L < R) {
9int mid = (L + R) / 2;
10if (check(x, mid))     R = mid;
11else L = mid + 1;  
12}
13return a［L］;
14}
15public static void main(String［］ args) {
16int n = 100;
17for (int i = 1; i <=n; i++)   a［i］ = i;  
18int x = 68;
19System.out.println("x=" + bin_search(n, x));
20}
21}



二分法把长度为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个因子5，共6个因子5，所以尾零有6个。

(1) 通过30%的测试。

简单的方法是检查每个n，计算n!的尾零数量，尾零数量等于k的n就是答案。下面代码中第6行的for循环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。




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5long k = sc.nextLong();  
6for (long n = 5;; n += 5) {
7long cnt = check(n);
8if (cnt == k) {
9System.out.println(n);
10break;
11}
12if (cnt > k) {
13System.out.println(-1);
14break;
15}
16}
17} 
18public static long check(long n) {
19long cnt = 0;
20while (n > 0) 
21cnt += (n /= 5);  
22return cnt;
23}
24}



(2) 通过100%的测试。

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

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




1import java.util.Scanner;
2public class Main {
3public static long check(long n) {  //计算n!的末尾有多少个0
4long cnt = 0;
5while (n > 0) {
6cnt += n / 5;
7n /= 5;
8}
9return cnt;
10}
11public static void main(String［］ args) {
12Scanner scanner = new Scanner(System.in);
13long k = scanner.nextLong();
14long L = 0;
15long R = (long) Math.pow(10, 19);//R的初始值为一个极大的数
16while (L < R) {
17long mid = (L + R) / 2;
18if (check(mid) >= k)  //mid!的尾零数量超过k，说明mid大了
19R = mid;
20else   L = mid + 1;//mid小了
21}
22if (check(R) == k)    System.out.println(R);
23else System.out.println(-1);
24}
25}









 例5．92022年第十三届蓝桥杯省赛Java大学A组试题G： 青蛙过河 lanqiaoOJ 2097
时间限制: 1s内存限制: 512MB本题总分： 20分

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




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int n = sc.nextInt();
6int x = sc.nextInt();
7int［］ h = new int［n］;
8int［］ sum = new int［n］;
9sum［0］ = 0;
10for (int i = 1; i < n; i++) {
11h［i］ = sc.nextInt();
12sum［i］ = sum［i - 1］ + h［i］;//跳跃区间的高度之和
13}  
14int L = 1, R = n;
15while (L < R) {
16int mid = (L + R) / 2;
17if (check(sum, mid, x))   R = mid;
18elseL = mid + 1;
19}  


20System.out.println(L);
21} 
22private static boolean check(int［］ sum, int mid, int x) {
23for (int i = 1; i < sum.length - mid + 1; i++) 
24if (sum［i + mid - 1］ - sum［i - 1］ < 2 * x) 
25return false;     //每个区间的高度之和都要大于或等于2x
26return true;
27}
28}










 例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<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就是可行的。

代码第42行把二分mid写成mid=((R- L) 1)+L而不是mid=(R+L)  1，是因为R+L可能溢出。R的最大值是2E9，L的最大值是1E9，R+L超过了int的范围。为什么第39行定义R的初始值为2E9？请读者思考。




1import java.util.Scanner;
2public class Main {
3static int［］ L;
4static int［］ S;
5static int n;
6static int len;
7public static boolean check(int t) { //检查t时刻管道内是否都有水
8int cnt = 0;
9int last_L = 2;
10int last_R = 1;
11for(int i = 0; i < n; i++) {
12if(t >= S［i］) {  
13cnt++;     //判断t是否够大
14int left = L［i］ - (t - S［i］);
15int right = L［i］ + (t - S［i］);
16if(left < last_L) {
17last_L = left;
18last_R = Math.max(last_R, right);
19} else if(left <= last_R + 1) {
20last_R = Math.max(last_R, right);
21}
22}
23}
24if(cnt == 0) return false;
25if(last_L <= 1 && last_R >= len) return true;
26else return false;
27}
28public static void main(String［］ args) {
29Scanner scanner = new Scanner(System.in);
30n = scanner.nextInt();
31len = scanner.nextInt();
32L = new int［n］;
33S = new int［n］;
34for(int i = 0; i < n; i++) {
35L［i］ = scanner.nextInt();
36S［i］ = scanner.nextInt();
37}
38int LL = 0;    //LL避免和L［］重名
39int R = 2000000000;
40int ans = -1;
41while(LL <=R) {    //二分
42int mid = ((R - LL) >> 1) + LL;//如果写成(L+R)>>1可能溢出


43if(check(mid)) {
44ans = mid;
45R = mid - 1;
46} else    LL = mid + 1;  
47}
48System.out.println(ans);
49}
50}



下面是一道稍微有难度的二分法题目。







 例5．112022年第十三届蓝桥杯省赛Java研究生组试题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次，每次升级时选用攻击力最大的技能，然后更新它的攻击力。

下面是Java代码。复杂度是多少？第16行升级m次，复杂度是O(m)； 第19~22行找最大攻击力，复杂度是O(n)。总复杂度为O(mn)，只能通过40%的测试。




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4int［］ a = new int［1010］;//存ai、bi  
5int［］ b = new int［1010］;
6int［］ c = new int［1010］;//ci=ai/bi
7Scanner sc = new Scanner(System.in);


8int n = sc.nextInt();
9int m = sc.nextInt();
10for (int i = 0; i < n; i++) {
11a［i］ = sc.nextInt();
12b［i］ = sc.nextInt();
13c［i］ = (int) Math.ceil((double) a［i］ / b［i］);//向上取整
14}
15int ans = 0;
16for (int i = 0; i < m; i++) { //一共升级m次
17int max_num = a［0］;//每次升级时使用最大的攻击力
18int index = 0;     //找最大攻击力对应的序号
19for (int j = 1; j < n; j++) {
20if (a［j］ > max_num) {
21max_num = a［j］;
22index = j;
23}
24}
25a［index］ -= b［index］;//更新攻击力
26if (c［index］ > 0)    ans += max_num;//累加攻击力
27c［index］ -= 1;
28}
29System.out.println(ans);
30}
31}



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

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

下面用Java的优先队列PriorityQueue实现。




1import java.util.PriorityQueue;
2import java.util.Scanner;
3public class Main {
4public static void main(String［］ args) {
5PriorityQueue<Pair<Integer, Integer>> 
6q = new PriorityQueue<>((a, b) -> b.first - a.first);
7Scanner sc = new Scanner(System.in);
8int n = sc.nextInt();
9int m = sc.nextInt();
10for (int i = 0; i < n; i++) {
11int a = sc.nextInt();
12int b = sc.nextInt();
13q.add(new Pair<>(a, b));
14}
15long ans = 0;
16while (m > 0 && !q.isEmpty()) {  //升级m次
17Pair<Integer, Integer> p = q.poll(); 
18//每次升级时使用最大的攻击力，读队列的最大值并删除
19ans += p.first;  //累加攻击力
20p.first -= p.second;   //更新攻击力
21if (p.first > 0)  q.add(p);  //重新放进队列   
22m--;
23}
24System.out.println(ans);
25}

26static class Pair<T, U> {
27T first;
28U second;
29Pair(T first, U second) {
30this.first = first;
31this.second = second;
32}
33}
34}



(3) 二分法。

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

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

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

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

分析代码的复杂度。第27~30行，二分O(log2a)次，这里a表示1≤ai≤106； 每次check()是O(n)，二分的总复杂度是O(nlog2a)。第34行的for循环是O(n)。代码的总复杂度是O(nlog2a)+O(n)，通过100%的测试。




1import java.util.Scanner;
2public class Main {
3static int［］ a, b;
4static int n, m;
5public static boolean check(long mid){//最后一次技能升级，是否能到mid
6long cnt = 0;    //注意，此时需要用long
7for (int i = 0; i < n; ++i) {
8if (a［i］ < mid) //第i个技能的初始值还不够mid，不用这个技能  
9continue;  
10cnt += (a［i］ - mid) / b［i］ + 1;//第i个技能用掉的次数
11if (cnt >= m) //所有技能升级的总次数≥m，说明mid设小了
12return true; 
13}
14return false; //所有技能的升级总次数小于m，说明mid设大了
15}
16public static void main(String［］ args) {
17Scanner sc = new Scanner(System.in);
18n = sc.nextInt();
19m = sc.nextInt();
20a = new int［n］;
21b = new int［n］;
22for (int i = 0; i < n; ++i) {
23a［i］ = sc.nextInt();
24b［i］ = sc.nextInt();
25}
26long L = 1, R = 1000000;//二分枚举最后一次攻击力最大能加多少
27while (L <= R) {
28long mid = (L + R) / 2;
29if (check(mid))  L = mid + 1;//增加mid
30else   R = mid - 1;    //减小mid  
31}
32long attack = 0;
33long cnt = m;
34for (int i = 0; i < n; ++i) {
35if (a［i］ < R)  continue; 
36long t = (a［i］ - L) / b［i］ + 1;//第i个技能升级的次数
37if (a［i］ - b［i］ * (t - 1) == R) 
38t -= 1;  //这个技能每次升级刚好等于R，比其他技能更好 
39attack += (a［i］ * 2 - (t - 1) * b［i］) * t / 2;
40cnt -= t;
41}
42System.out.println(attack + cnt * R);
43}
44}



【练习题】

二分的题目非常多，每个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






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




1import java.util.*;
2class Main {
3static class Gold { double w, v, p; }
4public static void main(String［］ args) {
5Scanner sc = new Scanner(System.in);
6int n = sc.nextInt();
7int c = sc.nextInt();
8Gold［］ a = new Gold［n］;
9for (int i = 0; i < n; i++) {
10a［i］ = new Gold();
11a［i］.w = sc.nextDouble();
12a［i］.v = sc.nextDouble();
13a［i］.p = a［i］.v/a［i］.w;
14}
15Arrays.sort(a, new Comparator<Gold>() {
16public int compare(Gold a, Gold b) {
17return Double.compare(b.p, a.p);
18}
19});
20double sum = 0.0;
21for (int i = 0; i < n; i++) {
22if (c >= a［i］.w) {
23c -= a［i］.w;
24sum += a［i］.v;
25} else {
26sum += c * a［i］.p;
27break;
28}
29}
30System.out.printf("%.2f", sum);
31}
32}



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

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


输入样例： 

3

0 2

2 4

1 3输出样例： 

2





按策略(2)编码。




1import java.util.*;
2class Main {
3static class Data { int L, R; }     //开始时间、结束时间

4public static void main(String［］ args) {
5Scanner sc = new Scanner(System.in);
6int n = sc.nextInt();
7Data［］ a = new Data［n］;
8for (int i = 0; i < n; i++) {
9a［i］ = new Data();
10a［i］.L = sc.nextInt();
11a［i］.R = sc.nextInt();
12}
13Arrays.sort(a, new Comparator<Data>() {
14public int compare(Data x, Data y) {
15return x.R - y.R;
16}
17});
18int ans = 0;
19int lastend = -1;
20for (int i = 0; i < n; i++) 
21if (a［i］.L >= lastend) {
22ans++;
23lastend = a［i］.R;
24}
25System.out.println(ans);
26}
27}



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





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




1import java.util.*;
2class Main {
3static class Data {long L, R;}
4public static void main(String［］ args) {
5Scanner sc = new Scanner(System.in);
6int n = sc.nextInt();
7Data［］ a = new Data［n］;
8for (int i = 0; i < n; i++) {
9a［i］ = new Data();
10a［i］.L = sc.nextLong();
11a［i］.R = sc.nextLong();
12}
13Arrays.sort(a, new Comparator<Data>() {
14public int compare(Data x, Data y) {
15return Long.compare(x.L, y.L);
16}
17});
18long lastend = -1;
19long ans = 0;
20for (int i = 0; i < n; i++) 
21if (a［i］.R >= lastend) {
22ans += a［i］.R - Math.max(lastend, a［i］.L) + 1;
23lastend = a［i］.R + 1;
24}
25System.out.println(ans);
26}
27}



5．5．2例题

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







 例5．152023年第十四届蓝桥杯省赛Java大学C组试题E： 填充lanqiaoOJ 3519
时间限制: 3s内存限制: 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)即可。在代码中只有一个for循环，计算复杂度为O(n)。




1import java.util.Scanner;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5String s = sc.next();
6int ans = 0;
7for (int i = 0; i < s.length() - 1; i++) {
8if (s.charAt(i) == s.charAt(i + 1)) {
9ans++;
10i++;
11}
12else if (s.charAt(i) == '?' || s.charAt(i + 1) == '?') {
13ans++;
14i++;

15}
16}
17System.out.println(ans);
18}
19}










 例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的商品，由于价格已经排序，可以用二分法减少查找的时间。在C++STL中自带了二分查找函数lowerBound()，但是Java没有自带二分函数，下面自己写一个二分函数。




1import java.util.Arrays;
2import java.util.Scanner;
3public class Main {
4public static void main(String［］ args) {
5Scanner sc = new Scanner(System.in);
6int n = sc.nextInt();
7int［］ a = new int［n］;
8for (int i = 0; i < n; i++)
9a［i］ = sc.nextInt();
10Arrays.sort(a);
11long ans = 0;
12int cnt = 0;
13int last = -1;
14int last_id = n - 1;
15boolean［］ vis = new boolean［n］;
16for (int i = n - 1; i >= 0; i--) {
17if (!vis［i］) {
18cnt++;
19ans += a［i］;
20last = a［i］;
21}
22if (cnt == 2) {
23cnt = 0;
24int x = lowerBound(a, 0, last_id, last / 2);
25if (x > last_id || a［x］ > last / 2) x--;
26if (x >= 0) {
27vis［x］ = true;
28last_id = x - 1;
29}
30}
31}
32System.out.println(ans);
33}
34private static int lowerBound(int［］ a, int L, int R, int target) { 
35//二分查找
36while (L < R) {
37int mid = L + (R - L) / 2;
38if (a［mid］ >= target)  R = mid;
39else L = mid + 1;
40}
41return L;
42}
43}










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




1import java.util.Arrays;
2import java.util.Scanner;
3public class Main {
4public static void main(String［］ args) {
5Scanner input = new Scanner(System.in);
6int x = input.nextInt();
7int n = input.nextInt();
8int［］ a = new int［n］;
9for (int i = 0; i < n; i++)     a［i］ = input.nextInt();  
10Arrays.sort(a);
11if (a［0］ != 1) {  System.out.println(-1);  return; }
12int s = 0;
13int ans = 0;
14while (s < x) 
15for (int v = n - 1; v >= 0; v--) 
16if (a［v］ <= s + 1) {
17s += a［v］;
18ans++;
19break;
20}
21System.out.println(ans);
22}
23}











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



1import java.util.*;
2class Main {
3static class aa { int l, r; }
4public static void main(String［］ args) {
5Scanner sc = new Scanner(System.in);
6int n = sc.nextInt();
7aa［］ a = new aa［n + 1］;
8for (int i = 1; i <= n; i++) {
9int x = sc.nextInt();
10int w = sc.nextInt();
11a［i］ = new aa();
12a［i］.l = x - w;
13a［i］.r = x + w;
14}
15Arrays.sort(a, 1, n+1, new Comparator<aa>() {  //按右端点排序
16public int compare(aa a, aa b) { return a.r - b.r;  }
17});
18int R = a［1］.r;
19int ans = 1;
20for (int i = 2; i <= n; i++) {
21//选剩下的活动中最早结束的活动，跳过冲突的活动
22if (a［i］.l >= R) {
23R = a［i］.r;
24ans++;
25}
26}
27System.out.println(ans);
28}
29}









 例5．19奶牛优惠券https://www．luogu．com．cn/problem/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： 

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

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

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




1import java.util.*;
2public class Main {
3public static void main(String［］ args) {
4Scanner sc = new Scanner(System.in);
5int n = sc.nextInt();
6int k = sc.nextInt();
7long m = sc.nextLong();
8int［］ p = new int［n + 1］;
9int［］ c = new int［n + 1］;
10boolean［］ buy = new boolean［n+1］;//buy［i］=1: 第i个物品被买了
11PriorityQueue<int［］> P = new PriorityQueue<>((a, b) -> a［0］ - b［0］);
12PriorityQueue<int［］> C = new PriorityQueue<>((a, b) -> a［0］ - b［0］);
13PriorityQueue<Integer> D = new PriorityQueue<>();
14for (int i = 1; i <= n; i++) {
15p［i］ = sc.nextInt();
16c［i］ = sc.nextInt();
17P.add(new int［］{p［i］, i});  
18//原价，还没买的在这里，如果买了就移出去
19C.add(new int［］{c［i］, i});  
20//优惠价，还没买的在这里，如果买了就移出去
21}
22for (int i = 1; i <= k; i++) 
23D.add(0);     //k张优惠券，开始时每个优惠为0
24long ans = 0;
25while (!P.isEmpty() && !C.isEmpty()) {
26int［］ p1 = P.peek();     //取出原价最便宜的
27int［］ c2 = C.peek();     //取出优惠价最便宜的
28if (buy［p1［1］］) { P.poll();  continue; } //这个已经买了，跳过
29if (buy［p1［1］］) { P.poll();  continue; } //这个已经买了，跳过
30if (D.peek() > p1［0］ - c2［0］) {  
31//用原价买i更划算，不用替换优惠券
32m -= p1［0］;//买原价最便宜的
33P.poll(); //这里不要C.pop()，因为买的是p1，不是c2
34buy［p1［1］］ = true;   //标记p1买了
35} else {  //替换优惠券
36m -= c2［0］ + D.peek();     //买优惠价最便宜的

37C.poll(); //这里不要p.pop()，因为买的是c2，不是p1
38buy［c2［1］］ = true;     //标记c2买了
39D.poll();  //原来用优惠券的退回优惠券
40D.add(p［c2［1］］ - c［c2［1］］);    
41//c2使用优惠券，重新计算delta并进队列
42}
43if (m >= 0)    ans++;
44else     break;
45}
46System.out.println(ans);
47}
48}



【练习题】

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

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




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

在本书第2章的“2．1 杂题和编程能力”曾提到计算思维的作用，通过做杂题可以帮助大家建立基本的、自发的计算思维。在计算机科学中有大量经典的算法和数据结构。在这些知识点中，基本算法易于理解、适用面广、精巧高效，是计算思维的基础，真正的计算思维从这里开始。

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