文章目录
展开本部分介绍一些基础的算法。
掌握这些算法是学习进阶算法的前提。
3.0 复杂度
时间复杂度和空间复杂度是衡量算法效率的重要标准。
3.0.0 基本操作数
由于配置不同，同一个算法在不同计算机上运行的速度会有一定差别，并且实际运行速度难以在理论上进行计算，实际测量又比较麻烦，所以我们通常不考虑算法的实际用时，而是算法运行所需要进行的基本操作的数量。
在普通的计算机上，加减乘除、访问变量、给变量赋值都可以看作基本操作。
对基本操作的计数或估测可以作为评判算法用时的指标。
3.0.1 时间复杂度
定义
衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据规模，一般指输入的数字个数等。一般来说，数据规模越大，算法的用时越长。而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势。
引入
考虑用时随数据规模变化的趋势的主要原因有以下几点：
- 现代计算机每秒可以处理数以亿计（1\times10^9）乃至更多次计算，因此我们处理的数据规模通常很大。如果算法A在规模为 n 的数据上用时为 100n 而算法B在规模为 n 的数据上用时为 n^2 ，在数据规模小于100时算法B用时更短，但在一秒钟内算法A可以处理数百万（1\times10^7）规模的数据，而算法B只能处理数万（1\times10^5）规模的数据。在允许算法执行时间更久时，时间复杂度对可处理数据规模的影响就会更加明显，远大于同一数据规模下用时的影响。
- 我们采用基本操作数来表示算法的用时，而不同的基本操作实际用时是不同的，例如加减法的用时远小于除法的用时。计算时间复杂度而忽略不同基本操作之间的区别，可以消除基本操作用时不同的影响。
当然，算法的运行用时并非完全由输入规模决定，而是也与输入的内容有关。比如我们给出n*m个数，其中每行一个质数，要求找出每行的质数。如果所有质数都在第一列，那么找到后直接break就会节省很多时间。但是测试数据不是我们能决定的。所以，时间复杂度又分为几种，例如：
- 最坏时间复杂度，即每个输入规模下用时最长的输入对应的时间复杂度（对应上例，假设我们必须遍历每一行所有数字才能找到那那个质数）。在算法竞赛中，由于输入可以在给定的数据范围内任意给定，我们为保证算法能够通过某个数据范围内的任何数据，一般考虑最坏时间复杂度。
- 平均（期望）时间复杂度，即每个输入规模下所有可能输入对应用时的平均值的复杂度（随机输入下期望用时的复杂度）。
期望：语文：100，数学：90，英语：80。成绩的算术平均分：90。
语文：数学：英语=3:2:1,加权平均分：100*0.5+90*1/3+80*1/6=93。
m个数，找哪个是质数。
最坏时间复杂度：m次。
平均时间复杂度：1*1/m+2*1/m+….m*1/m=(1+m)/2次。
所谓“用时随数据规模而增长的趋势”是一个模糊的概念，我们需要借助下文所介绍的渐进符号来形式化地表示时间复杂度。
3.0.2 渐进符号的定义
渐进符号是函数的阶的规范描述。简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作“常数”），而保留了可以用来表明该函数增长趋势的重要部分。
y=n^3+n^2+n+1,\ n=1,y=4;n=10,y=1111,n=100,y=1010101,n=1000,y=1001001001.
大Θ符号
对于函数 f(n) 和 g(n) ，f(n)=\Theta(g(n))，当且仅当 \exist c_1,c_2,n_0>0， 使得 \forall n\geq n_0,0\leq c1·g(n)\leq f(n)\leq c_2·g(n) 。
也就是说，如果函数 f(n)=\Theta(g(n))，那么我们能找到两个正数 c_1, c_2 使得 f(n) 被 c1·g(n) 和 c_2·g(n) 夹在中间。
例如，3n^2+5n-3=\Theta(n^2)，这里的 c_1,c_2,n_0 可以分别是 2,4,100。
当 n\geq100 时，2n^2\leq 3n^2+5n-3\leq4n^2 。
n\sqrt{n}+nlog^5n+mlogm+nm=\Theta(n\sqrt{n}+mlogm+nm)，这里的 c_1,c_2,n_0 可以分别是 1,2,100。
当 n\geq100 时，\sqrt{n}\geq log^5n 。
大Ο符号
\Theta 符号同时给了我们一个函数的上下界，如果只知道一个函数的渐进上界而不知道其渐进下界，可以使用 \mathrm{O} 符号。
f(n)=\mathrm{O}(g(n))，当且仅当 \exist c,n_0， 使得 \forall n\geq n_0,0\leq f(n)\leq c·g(n) 。
研究时间复杂度时通常会使用 \mathrm{O} 符号，因为我们关注的通常是程序用时的上界，而不关心其用时的下界。
需要注意的是，这里的「上界」和「下界」是对于函数的变化趋势而言的，而不是对算法而言的。算法用时的上界对应的是「最坏时间复杂度」而非大 \mathrm{O} 记号。所以，使用 \Theta 记号表示最坏时间复杂度是完全可行的，甚至可以说 \Theta 比 \mathrm{O} 更加精确，而使用 \mathrm{O} 记号的主要原因，一是我们有时只能证明时间复杂度的上界而无法证明其下界（这种情况一般出现在较为复杂的算法以及复杂度分析)，二是 \mathrm{O} 在电脑上输入更方便一些。
大Ω符号
同样的，我们使用 \Omega 符号来描述一个函数的渐进下界。
f(n)=\Omega(g(n))，当且仅当 \exist c,n_0， 使得 \forall n\geq n_0,0\leq c·g(n)\leq f(n) 。
小ο符号
如果说 \mathrm{O} 序号相当于小于等于号，那么 \omicron 符号就相当于小于号。
f(n)=\omicron(g(n))，当且仅当 \exist c,n_0， 使得 \forall n\geq n_0,0\leq f(n)< c·g(n) 。
小 \omicron 符号大量应用于数学分析中，函数在某点处的泰勒展开式拥有皮亚诺余项，使用小 \omicron 符号表示严格小于，从而进行等价无穷小的渐进分析。
小ω符号
如果说 \Omega 序号相当于大于等于号，那么 \omega 符号就相当于大于号。
f(n)=\omega(g(n))，当且仅当 \exist c,n_0， 使得 \forall n\geq n_0,0\leq c·g(n)< f(n) 。
常见性质
· f(n)=\Theta(g(n))\Leftrightarrow f(n)=\mathrm{O}(g(n))∧ f(n)=\Omega(g(n))
· f_1(n)+f_2(n)=\mathrm{O}(max(f_1(n),f_2(n))
· f_1(n)\times f_2(n)=\mathrm{O}(f_1(n)\times f_2(n))
· \forall a\neq1,log_an=\mathrm{O}(log_2n) 。由换底公式 log_an=\frac{log_2n}{log_2a} 可知，任何对数函数无论底数为何，都具有相同的增长率，因此渐进时间复杂度中对数的底数一般省略不写。
3.0.3 时间复杂度计算的例子
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<m;k++){ cout<<"Hello World!"<<endl; } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<m;k++){ cout<<"Hello World!"<<endl; } } } for(int i=0;i<n;i++){ cout<<"Hello C++!"<<endl; } return 0; } |
如果以输入的数值 n 和 m 的大小作为规模，则上面这段代码的时间复杂度为 2n^2m+n=O(n^2m)。
3.0.4 哪些量是常量？
当我们要进行若干次操作时，如何判断这若干次操作是否影响时间复杂度呢？例如：
|
1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> using namespace std; int main() { const int N=100000; for(int i=0;i<N;i++){ cout<<"Hello World!"<<endl; } return 0; } |
如果 n 的大小不被看作输入规模，那么这段代码的时间复杂度就是 O(1)。
进行时间复杂度计算时，哪些变量被视作输入规模是很重要的，而所有和输入规模无关的量都被视作常量，计算复杂度时可当作 1 来处理。
3.0.5 空间复杂度
类似地，算法所使用的空间随输入规模变化的趋势可以用 空间复杂度 来衡量。
3.1 模拟
3.1.0 概念
模拟就是用计算机来模拟题目中的要求。
模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以差错的情况，如果在考试中写错是相当浪费时间的。
3.1.1 技巧
写模拟题时，遵循以下的建议有可能会提升做题速度：
- 在动手写代码之前，在草纸上尽可能地写好要实现的流程。
- 在代码中，尽量把每个部分模块化，写成函数或结构体。在关键的地方添加注释方便自己理解。
- 对于一些可能重复用到的概念，可以统一转化，方便处理：如，某题给你”YY-MM-DD 时:分”，把它抽取到一个函数，处理成秒，会减少概念混淆。
- 调试时分块调试。模块化的好处就是可以方便的单独调某一部分。
- 写代码的时候一定要思路清晰，不要想到什么就写什么，要按照落在纸上的步骤写。
实际上，上述步骤在解决其它类型的题目时也是很有帮助的。
3.1.2 例题
3.1.2.0 Climbing Worm
一只长度不计的蠕虫位于 n 英寸深的井的底部。它每次向上爬 u 英寸，但是必须休息一次才能再次向上爬。在休息的时候，它滑落了 d 英寸。之后它将重复向上爬和休息的过程。蠕虫爬出井口需要至少爬多少次？如果蠕虫爬完后刚好到达井的顶部，我们也设作蠕虫已经爬出井口。
解题思路
直接使用程序模拟蠕虫爬井的过程就可以了。用一个循环重复蠕虫的爬井过程，当攀爬的长度超过或者等于井的深度时跳出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; int main() { int u, d, n; cin>>u>>d>>n; int time=0, dist=0; while(true){ dist+=u; time++; if(dist>=n)break; dist-=d; } cout<<time<<endl; return 0; } |
3.1.2.1 天天爱跑步
题面不再重复，点链接即可。
解题思路
循环每天，用一变量 day 记录连续多少天签到即可。当天签到时 day++ ，当天未签到时 day=0 。
3.2 枚举
3.2.0 概念
枚举（Enumerate）是基于已有知识来猜测答案的一种问题求解策略。
枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。
3.2.1 技巧
3.2.1.0 给出解空间
建立简洁的数学模型。
枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？
3.2.1.1 减少枚举的空间
枚举的范围是什么？是所有的内容都需要枚举吗？
在用枚举法解决问题的时候，一定要想清楚这两件事，否则会带来不必要的时间开销。
例：求素数，理论时间复杂度 O(n^2) ，实际要低于此。
3.2.1.2 选择合适的枚举顺序
根据题目判断。比如下面例题中要求的是最大的符合条件的素数，那自然是从大到小枚举比较合适。
3.2.2 例题
3.2.2.0 求数对
一个数组中的数互不相同，求其中和为 0 的数对的个数。
解题思路
最基础的思路是枚举两个数，判断其相加是否等于零。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> using namespace std; int a[1000010]; int main() { int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(a[i]+a[j]==0){ ans++; } } } cout<<ans<<endl; return 0; } |
这段代码的时间复杂度为 O(n^2) 。接下来看看如何优化。
由于题中没要求数对是有序的，答案就是有序的情况的两倍，即如果 (a, b) 是答案，那么 (b, a) 也是答案。对于这种情况，只需统计有序后的答案，最后再乘 2 就好了。
不妨按照读入顺序有序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> using namespace std; int a[1000010]; int main() { int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<i;j++){ if(a[i]+a[j]==0){ ans++; } } } cout<<ans*2<<endl; return 0; } |
这里我们减少了 j 的枚举范围，虽然代码的时间复杂度还是 O(n^2) ，但是其会比上一段代码更快。
再考虑，两个数是否都一定要枚举出来呢？
其实，枚举其中一个数后，题目的条件已经确定了其他的要素（另一个数）的条件，如果能找到一种方法直接判断题目要求的那个数是否存在，就可以省掉枚举后一个数的时间了。
比较进阶地，在数据范围允许的情况下，我们可以利用桶记录遍历过的数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> using namespace std; int a[1000010]; const int MAXN = 4000000; // 假设数组中的数字ai满足-4000000<=ai<=4000000 bool met[MAXN*2+10]; // 声明为全局变量，使其默认全部赋值为零 int main() { int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int ans=0; for(int i=1;i<=n;i++){ if(met[MAXN-a[i]]){ // a[i]的相反数为-a[i], 我们判断桶中是否有-a[i]. 如果有，即可和a[i]构成一套答案 ans++; } met[MAXN+a[i]]=true; // 由于数据范围为-4000000~4000000, 因此我们将所有数字向后平移4000000个，即数组下标为0~8000000 } cout<<ans*2<<endl; return 0; } |
最后，这段代码被我们优化到了 O(n) 的时间复杂度，其空间复杂度为 O(n+max{|x|:x\in a}) 。
3.3 递归
3.3.0 概念
递归（Recursion），在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类但规模更小的子问题而解决问题的方法。
递归是计算机科学中的一个重要概念。不仅仅在算法中经常使用，在我们进行计算机相关其他学科的学习时（甚至一些数学定义，如自然数的定义），一些定义或者结构都可能采取递归的方式。一个有趣的例子。
在算法竞赛中，一个函数直接或间接调用自己本身，则其称为递归函数。由此可见，递归函数必须有一个结束条件，否则该函数就会无穷无尽的调用下去了。
3.3.1 引入
要理解递归，就得先理解什么是递归。
递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。
以下是一些有助于理解递归的例子：
- 什么是递归？
- 如何给一堆数字排序？答：分成两半，先排左半边再排右半边，最后合并就行了。至于怎么排左边和右边，请重新阅读这句话。（此为归并排序）
- 你今年几岁？答：去年的岁数加一岁，2002年我出生。
递归在数学中非常常见。例如，集合论对自然数的正式定义是：0是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。
递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案。
|
1 2 3 4 5 6 7 |
int func(传入数值){ if(终止条件){ return 最小子问题解; } return func(缩小规模); } |
3.3.2 为什么要写递归
- 结构清晰，可读性强。例如，分别用不同的方法实现归并排序：
12345678910111213141516171819// 不使用递归的归并排序算法template <typename T>void merge_sort(vector<T> a) {int n = a.size();for (int seg = 1; seg < n; seg = seg + seg)for (int start = 0; start < n - seg; start += seg + seg)merge(a, start, start + seg - 1, std::min(start + seg + seg - 1, n - 1));}// 使用递归的归并排序算法template <typename T>void merge_sort(vector<T> a, int front, int end) {if (front >= end) return;int mid = front + (end - front) / 2;merge_sort(a, front, mid);merge_sort(a, mid + 1, end);merge(a, front, mid, end);}
显然，递归版本比非递归版本更易理解。递归版本的做法一目了然：把左半边排序，把右半边排序，最后合并两边。而非递归版本看起来不知所云，充斥着各种难以理解的边界计算细节，特别容易出bug，且难以调试。
-
练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时，递归写多了就能敏锐发现这个特点，进而高效解决问题。
3.3.3 递归的缺点
在程序执行中，递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成 栈溢出 的后果。
显然有时候递归是高效的，比如归并排序；有时间是低效的，比如数孙悟空身上的毛，因为堆栈会消耗额外空间，而简单的递推不会消耗空间。 、
3.3.4 一些要点
- 明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节， 否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。
-
递归和枚举的区别：枚举是横向地把问题划分，然后依次求解子问题；而递归是把问题逐级分解，是纵向的拆分。
-
记忆化搜索：记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。
举例：当我们求斐波那契数列时，我们可以写成：
123456int fib(int x){if(x==1||x==2)return 1;return fib(x-1)+fib(x-2);}但是这会导致重复调用，如求fib(13)时会调用fib(12)和fib(11)，但求fib(12)时又会调用fib(11)，所以我们完全可以在第一次求fib(11)时将其记录下来，下次再需要就不用再求了。
12345678int a[10000]={0,1,1};int fib(int x){a[x-1]=a[x-1]?a[x-1]:fib(x-1);a[x-2]=a[x-2]?a[x-2]:fib(x-2);return a[x-1]+a[x-2];}
3.3.5 例题
3.3.5.0 最大公约数和最小公倍数
给定两个数a和b，求二者的最大公因数（gcd）和最小公倍数（lcm）。
解题思路
求最大公因数有更相减损法和辗转相除法，二者原理类似。
辗转相除法即为：gcd(a,b)=gcd(b,a\%b) ，当b=0时，a即为答案。证明见百度百科 。
而又有定理：a\times b=gcd(a,b)\times lcm(a,b) ，即可求最小公倍数。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> using namespace std; int gcd(int a,int b) { if(b==0)return a; return gcd(b,a%b); } int main() { int a,b; cin>>a>>b; cout<<gcd(a,b)<<" "<<1LL*a*b/gcd(a,b)<<endl; return 0; } |
3.3.5.1 [NOIP2001 普及组] 求先序排列
给出一棵树的中序和后序排列，求它的先序排列。
解题思路
我们用后序排列确定树的根，然后在中序排列中将树划分为两部分，再分别递归求解子树即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; string z,h; bool find(int zl,int zr,int hl,int hr) { int i; //在中序遍历中找根 for(i=zl;i<=zr;i++) { if(z[i]==h[hr]) { break; } } cout<<z[i]; if(i!=zl)find(zl,i-1,hl,hl+i-1-zl); //如果有左子树则遍历左子树 if(i!=zr)find(i+1,zr,hr+i-zr,hr-1); //如果有右子树则遍历右子树 } int main() { cin>>z>>h; int len=z.length()-1; find(0,len,0,len); return 0; } |
如果你善用C++的string STL库函数，那么代码可以更易读：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<iostream> using namespace std; void find(string z,string h) { int len=z.size(); if(len<=0)return; char ch=h[len-1]; cout<<ch; int k=z.find(ch); //z.fine(ch)会返回z中第一处出现ch的下标 find(z.substr(0,k),h.substr(0,k)); //z.substr(i,len)表示从下标i的位置截取长度为len的子串 find(z.substr(k+1),h.substr(k,len-k-1)); } int main(){ string z,h; cin>>z>>h; find(z,h); return 0; } |
3.4 贪心
3.4.0 概念
贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值（较优解）的解题方法。
贪心策略总是做出在 当前看来 是最优的选择。也就是说，贪心并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解。所以我们在利用贪心算法解决问题时往往要证明该题目使用该贪心算法是正确的。（实际上，在具体问题中，我们如果能猜测一道题使用贪心是正确的，或使用贪心能获得较优解即可使用贪心。由于NOI系列竞赛中有部分分的概念，所以如果我们不能想出一道题的正确解法，而可以利用贪心获得较优解时就应该使用。）
一般来说，一个问题使用贪心算法是一定要证明该贪心算法是正确的。一般采用的策略是假设存在最优解，然后证明贪心得到的解就是最优解或比贪心得到的解更优的解不存在。但还是如上文所说，真正在赛场上实现算法时，严谨的证明还是不需要的。
3.4.1 引例
在n行m列的正整数矩阵中，要求从每行中选一个数，使得选出的n个数的和最大。
显然的，我们每次选相应行中最大的数即可。
3.4.2 反例
设定有n台处理机 p_1,p_2,…,p_n ，和m个作业 j_1,j_2,…,j_m ，处理机可并行工作，作业未完成不能中断，作业 j_i 在处理机上的处理时间为 t_i ，求解最佳方案，使得完成m个作业的时间最短。
贪心策略即为：将任务从大到小排序后，每次将作业加到最先空闲的机器上。
考虑如下例子：n=3，m=6，t={11, 7, 5, 5, 4, 7}。
贪心策略得到的时间是15，而搜索算法（枚举所有可能）的时间为14。
但是贪心策略会提供一个线索，那就是每台处理机上的时间不超过15，为搜索提供了方便。
3.4.3 技巧
总之，贪心算法不能保证求得的最后解是最佳的解，一般用来求某些最大或最小解的问题，能确定某些问题的可行解的范围，特别是给搜索算法提供了依据。
贪心算法的特点如下：
（1）贪心选择性：所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到，贪心法通常以自顶向下的方式作出一系列的贪心选择。确定是否有贪心选择性质
- 通常先考察问题的一个整体最优解，并证明可修改这个最优解，使其从贪心选择开始
-
作出贪心选择后，原问题简化为规模较小的类似子问题
-
用数学归纳法证明，通过每一步贪心选择，最终可得到问题的整体最优解
（2）最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理，问题的最优子结构性质是该问题可以用动态规划法或贪心法求解的关键特征。
3.4.4 例题
3.4.4.0 找零问题
一个小孩用1美元来买价值不足1美元的糖果，售货员希望用数量最少的硬币找给小孩零钱。假设售货员只有14美分、12美分、5美分和1美分的硬币。
1）设计贪心算法来解决找零问题（描述算法的贪心策略并给出算法伪代码）。
2）所设计的贪心算法能保证得到最优解吗？证明你所给的结论。
解题思路
1）设计的贪心算法如下：
假设需要找 x(0 \leq x \leq 100) 美分。先用 14 美分的硬币找零，即找零 n_{14}=\lfloor \frac x {14} \rfloor 枚 14 美分的硬币；再用 12 美分的硬币找零，即找零 n_{12}=\lfloor \frac{(x-14\times n_{14})} {12} \rfloor 枚 12 美分的硬币；然后用 5 美分的硬币找零，即找零 n_5=\lfloor \frac{(x-14\times n_{14}-12\times n_{12})} 5 \rfloor 枚 5 美分的硬币；最后用 1 美分的硬币找零，即找零 n_1=(x-14\times n_{14}-12\times n_{12}-5\times n_5) 枚 1 美分的硬币。最终答案为：找零 n_{14} 枚 14 美分、 n_{12} 枚 12 美分、n_5 枚 5 美分和 n_1 枚 1 美分的硬币满足题意。
实例代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> using namespace std; int main() { int x; cin>>x; int n14,n12,n5,n1; n14=x/14;//14美分硬币数 n12=(x-14*n14)/12;//12美分硬币数 n5=(x-14*n14-12*n12)/5;//5美分硬币数 n1=x-14*n14-12*n12-5*n5;//1美分硬币数 printf("Change %d 14 cents, %d 12 cents, %d 5 cents, %d 1 cents.\n",n14,n12,n5,n1); printf("A total of %d coins are required.\n",n14+n12+n5+n1); return 0; } |
2）证明上述贪心算法：
假设上述算法得到的不是最优解，则一定存在一个最优解记为{n_{14}’枚14美分硬币、n_{12}’枚12美分硬币、n_{5}’枚5美分硬币、n_{1}’枚1美分硬币}，使得n_{14}’+n_{12}’+n_{5}’+n_{1}'<n_{14}+n_{12}+n_{5}+n_{1}。
因为两个解都是可行解，所以有14\times n_{14}’+12\times n_{12}’+5\times n_{5}’+n_{1}’ = 14\times n_{14}+12\times n_{12}+5\times n_{5}+n_{1}.
因为n_{14}为需要找零x美分的情况下最大能找的14美分硬币数，所以n_{14}’ \leq n_{14}.
假设n_{14}’＜n_{14}，则说明有若干个14美分需要由剩下的三种硬币找零。每14美分可以由1枚12美分+2枚1美分或2枚5美分+4枚1美分或14枚1美分找零，均大于1枚硬币。因此这种假设得到的不可能是最优解。
所以n_{14}’=n_{14}.
因此问题转化为用12美分、5美分、1美分硬币找零0\leq x-14\times n_{14}<14美分的子问题。
子问题证明思路同上，所以有n_{12}’=n_{12},n_{5}’=n_{5},n_{1}’=n_{1}.
所以n_{14}’+n_{12}’+n_{5}’+n_{1}’ = n_{14}+n_{12}+n_{5}+n_{1}，即上述贪心算法得到的就是最优解。
3.4.4.1 [NOIP2010 普及组] 接水问题
贪心策略很简单：下一名接水的同学一定是去目前所有正在接水的同学中最早接完的那里。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include<bits/stdc++.h> using namespace std; int n,m,x,a[100001]; int main(){ cin>>n>>m; for(int i=0;i<m;i++) { cin>>a[i]; } for(int i=m;i<n;i++){ cin>>x; int minn=9999,minnn=0; for(int j=0;j<m;j++){ if(minn>a[j]){ minn=a[j]; minnn=j; } } a[minnn]+=x; } x=-1; for(int i=0;i<m;i++){ if(a[i]>x){ x=a[i]; } } cout<<x; return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> using namespace std; int n,m; int a[10010]; int b[110]; //b[i]表示第i个水龙头用了多少水 int main() { cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=m;i++)b[i]+=a[i]; for(int i=m+1;i<=n;i++) { int minn=b[1],t=1; for(int j=2;j<=m;j++) { if(b[j]<minn) { minn=b[j]; t=j; } } b[t]+=a[i]; } int ans=0; for(int i=1;i<=m;i++) { if(ans<b[i]) { ans=b[i]; } } cout<<ans<<endl; return 0; } |
3.4.4.2 [USACO05NOV] 奶牛玩杂技
我们要求总压扁指数最小，那么我们就要考虑压扁指数和什么有关？
它和自己的力量有关，和别人的体重有关。
但是换种思路来向，这头奶牛的体重又会影响别人的压扁指数。所以从整体上来看应该是体重和力量的一个关系决定了奶牛的排序。
我们取相邻的奶牛 a,b 。易证这两头奶牛的顺序不会影响其他奶牛的压扁指数。
假设 W_a+S_a<W_b+S_b 。设这两头奶牛上面的所有奶牛的体重和为 W 。
第一种情况，如果 a 在 b 上面，则 a 的压扁指数为 W-S_a ， b 的压扁指数为 W+W_a-S_b ；
第二种情况，如果 b 在 a 上面，则 a 的压扁指数为 W+W_b-S_a ， b 的压扁指数为 W-S_b 。易证这种情况的总压扁指数为 W+W_b-S_a （不考虑其他奶牛的压扁指数）。
该值一定大于第一种情况中的 W-S_a 。再将其与 W+W_a-S_b 做比较，易证 W+W_b-S_a 大。
所以，在 W_a+S_a<W_b+S_b 的情况下， b 在 a 上面会取得更大的总压扁指数。因此我们应该使 a 在 b 上面。
综上，我们只需按 W+S 排序，较小的在上，较大的在下即可满足题意。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 将一个数组从小到大排序： #include <iostream> #include <algorithm> using namespace std; int a[10]={0,5,6,3,2,7,1,8,9,4}; int main() { sort(a,a+10); // 第一个参数为"数组名+排序开始位置的下标"，第二个参数为"数组名+排序开始位置的下标+数组长度"/"数组名+排序结束位置的后一个下标" //如果数组从1开始存储，则写成sort(a+1,a+1+10),10代指数组长度 for(int i=0;i<10;i++) { cout<<a[i]<<" "; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// 将一个数组从大到小排序： #include <iostream> #include <algorithm> using namespace std; int a[10]={0,5,6,3,2,7,1,8,9,4}; bool cmp(int a, int b){return a>b;} int main() { sort(a,a+10,cmp); // 第一个参数为"数组名+排序开始位置的下标"，第二个参数为"数组名+排序开始位置的下标+数组长度"/"数组名+排序结束位置的后一个下标"，第三个参数为比较函数 //如果数组从1开始存储，则写成sort(a+1,a+1+10),10代指数组长度 for(int i=0;i<10;i++) { cout<<a[i]<<" "; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// 将一个结构体按照x为第一优先级从小到大，y为第二优先级从小到大排序： #include <iostream> #include <algorithm> using namespace std; struct node { int x,y; }; node a[5]; bool cmp(node a, node b) { if(a.x==b.x)return a.y<b.y; return a.x<b.x; } int main() { a[0].x=3;a[0].y=1; a[1].x=2;a[1].y=2; a[2].x=3;a[2].y=2; a[3].x=1;a[3].y=1; a[4].x=2;a[4].y=1; sort(a,a+5,cmp); // 第一个参数为"数组名+排序开始位置的下标"，第二个参数为"数组名+排序开始位置的下标+数组长度"/"数组名+排序结束位置的后一个下标"，第三个参数为比较函数 for(int i=0;i<5;i++) { cout<<a[i].x<<" "<<a[i].y<<endl; } return 0; } |
解题代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <algorithm> using namespace std; struct node { int w,s; }; int n; node a[50010]; bool cmp(node a, node b) { return a.w+a.s<b.w+b.s; } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].w>>a[i].s; } sort(a+1,a+1+n,cmp); // 第一个参数为排序开始的位置，第二个参数为排序结束的后一个位置，第三个参数为比较函数 int sum=a[1].w,ans=-a[1].s; for(int i=2;i<=n;i++) { int t=sum-a[i].s; ans=ans>t?ans:t; sum+=a[i].w; } cout<<ans<<endl; return 0; } |
3.5 二分
3.5.0 概念
二分法在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，判断解在哪个部分中并调整上下界，直到找到目标元素。每次二分后都将舍弃一半的查找空间，因此效率很高。
三分法用于求解凸性函数的极值问题。二分法适用于单调函数，当需要求凸性函数的极值点时，三分法便可以派上用场。使用二分法不能判断函数极值点在哪一部分，而三分法将区间分成三部分，可以明确地判断一定不在哪一部分，每次要舍弃三分之一的查找空间，效率也很高。
在实际求解中，有些问题很难直接求其最优解，但它符合单调性或凸性，对于给定的一个解，很容易求得这个解是否可行或者这个解的花费，一般这样的问题就需要用到二分法或三分法的思想快速求解。
3.5.1 引例
以在一个升序数组中查找一个数为例。
如果我们依此遍历这个数组，平均时间复杂度是 O(n) 的。
而我们使用二分法，每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。
例如有一串数 [1\ 3\ 4\ 5\ 6\ 7\ 9\ 11\ 13\ 15\ 17] ，如果我们要找 5 ，我们只需要：
- 左端点下标为 1 ，右端点下标为 11 ，中间点下标为 (1+11)/2=6 ，即 7 ，比 5 大，因此下标 6\sim11 都不可能有 5 ；
- 左端点下标仍为 1 ，更新右端点下标为 5 ，中间点下标为 (1+5)/2=3 ，即 4 ，比 5 小，因此下标 1\sim3 都不可能有 5 ；
- 更新左端点下标为 4 ，右端点下标仍为 5 ，中间点下标为 (4+5)/2=4 ，即 5 ，找到了。
|
1 2 3 4 5 6 7 8 9 10 11 |
//递归写法 int a[N+10]; int binary_search(int l,int r,int x) { if(l>r)return -1; //没找到 int mid=(l+r)>>1; //>>1等价于/2，为了防止溢出，也可以写成l+((r-l)>>1)的形式 if(a[mid]==x)return mid; if(a[mid]>x)return binary_search(l,mid-1,x); if(a[mid]<x)return binary_search(mid+1,r,x); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//非递归写法 int a[N+10]; int binary_search(int l,int r,int x) { int ret=-1; int mid; while(l<=r) { mid=l+((r-l)>>1); if(a[mid]<x)l=mid+1; else if(a[mid]>x)r=mid-1; else{ ret=mid; break; } } return ret; } |
3.5.2 二分答案
注意，这里的有序是广义的有序，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做 1 ，不满足看做 0 ，至少对于这个条件的这一维度是有序的）。换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值。
要求满足某种条件的最大值的最小可能情况（最大值最小化），首先的想法是从小到大枚举这个作为答案的「最大值」，然后去判断是否合法。若答案单调，就可以使用二分搜索法来更快地找到答案。因此，要想使用二分搜索法来解这种「最大值最小化」的题目，需要满足以下三个条件：
- 答案在一个固定区间内；
- 可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；
- 可行解对于区间满足一定的单调性。换言之，如果 x 是符合条件的，那么有 x+1 或者 x-1 也符合条件。（这样下来就满足了上面提到的单调性）
当然，最小值最大化是同理的。
3.5.3 例题
3.5.3.0【深基13.例1】查找
这道题与上面描述的差别在于要考虑重复数字的情况。
当 a[mid]==x 时，还应该继续向前寻找，且不应该抛去 a[mid] 。
但这样会导致卡在 l==r 的时候，因此我们增加判断即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> using namespace std; #define N 1000000 //递归写法 int a[N+10]; int binary_search(int l,int r,int x) { if(l==r) { if(a[l]==x)return l; return -1; } int mid=(l+r)>>1; //>>1等价于/=2，为了防止溢出，也可以写成l+((r-l)>>1)的形式 if(a[mid]>=x)return binary_search(l,mid,x); if(a[mid]<x)return binary_search(mid+1,r,x); } int main() { int n,m,x; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]); while(m--) { scanf("%d",&x); printf("%d ",binary_search(1,n,x)); } return 0; } |
3.5.3.1 进击的奶牛
如果考虑暴力搜索每头牛所在隔间的情况，那答案将是阶乘级别的。
如果考虑暴力枚举答案，由于两个隔间最远的距离为 10^9 ，因此答案是 O(10^9) 的。
由于答案有序，即对于这个「最大的最近距离」，不会有更大的值使得存在可行解（即能把所有牛安排进隔间的情况），因此我们可以考虑二分答案。
对于每个二分值，我们只需要考虑在这个二分值下能不能将所有牛安排进隔间，如果能，则在 mid\sim{r} 中继续找；否则在 l\sim{mid-1} 中找。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <algorithm> using namespace std; int n,c; int a[1000010]; bool check(int x)//check函数有点贪心的意思，即在满足x距离要求的情况下尽可能放更多的牛 { int t=a[1],cnt=1; for(int i=2;i<=n;i++) { if(a[i]-t>=x) { t=a[i]; cnt++; } } if(cnt>=c)return true; return false; } int play(int l,int r) { if(l==r)return l; int mid=(l+r)/2+1; if(check(mid))return play(mid,r); return play(l,mid-1); } int main() { scanf("%d%d",&n,&c); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+1+n); printf("%d\n",play(1,1000000000)); return 0; } |
考虑为什么是 (l+r)/2+1 ：
- 对于
(l,mid-1)，无论如何下一次的r都会变； - 但对于
(mid,r)，如果mid=(l+r)/2，则当l+1==r时有mid=l，则会陷入(l,r)的死循环，因此需要使mid=(l+r)/2+1来跳出循环。
同理，如果二分是 (mid+1,r) 和 (l,mid) 的话，用 mid=(l+r)/2 就更合适了。
3.6 搜索
3.6.0 概念
搜索是一种通过穷举所有可能的解的状态，来求得题目所要求的解或者最优解的方法，即通过枚举解的所有可能状态，来寻求一个解或者最优解。在这个过程中必须确保不会重复搜索已经搜索过的状态，否则会导致循环的产生。同时也要考虑总的状态数是否在可接受的范围内，否则会导致超时或者算法无法停止。
然而有些时候，看起来因为状态数太多而无法进行搜索的题目也可以通过各种剪枝的方法求出解。所谓剪枝，就是在搜索的过程中，有意地避开那些虽然也属于可达状态，但是绝对不会是所求解的情况，通过这种方式减少总的所需搜索的状态数，来达到在时限要求内求出解的目的。
3.6.1 流程
想要用搜索算法解题，首先，需要表示出题目的状态空间，即题目所描述的初始状态、可达状态和终结状态，并确定它们之间的转移条件。其次，需要提出一个合理的搜索方式，这个搜索方式必须保证可以到达所有可能的情况，并且不会导致死循环的出现。最后，需要估计这样做能否在题目所给定的时间和空间限定内解出答案，如果超过了时间和空间限定，是否可以通过剪枝或者改变搜索方式等方法来优化算法，以达到符合限制条件的目的。
3.6.2 宽度优先搜索（BFS）
宽度优先搜索（Breadth First Search, BFS），又称广度优先搜索，是基础搜索算法中的重要组成部分。
宽度优先搜索常常和图论结合，因此在学完图论后可以回来重新审视宽度优先搜索的知识点。
宽度优先搜索遍历类似于树的按层次遍历的过程。
假设从图中某一点 1 出发，发现 1 可以到达 2 ，此时记录下 2 这个顶点，但是并不从 2 继续搜索，而是依然寻找 1 可以到达的点，直到所有 1 可以到达的点都被记录下俩，再寻找最早被记录的点，即 2 ，从他开始重新按照这样的方式搜索，但是对于已经搜索到的点（如 1 ）则不再记录，只记录从 2 出发可以到达的之前没有到达过的点即可。
例如，对下面这个无向图进行宽度优先搜索遍历，首先访问 1 和 1 的邻接点 2 和 3 ，然后依次访问 2 的邻接点 4 和 5 以及 3 的邻接点 6 和 7 ，最后访问 4 的邻接点 8 。由于这些顶点的邻接点均已被访问，并且图中所有节点都被访问，由此完成了图的遍历。得到的顶点访问序列为：
1→2→3→4→5→6→7→8
在搜索遍历的过程中，需要使用数组 visit[maxn] 记录某个点是否在之前已经到达。同时，为了按照记录的顺序访问点，需要使用队列来记录所有第一次到达的点。
从图的某一顶点 v 出发，递归地进行宽度优先遍历的伪代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void BFS(){ //按广度优先遍历图G。使用队列Q和访问数组visit for(v=0;v<maxn;v++) visit[v]=false; Q.clear(); Q.push(start); //放入队头 while(!Q.empty()){ u=Q.front(); Q.pop(); //队头元素存在u中并出队 visited[u]=true; visit(u); //访问u if(!visited[w]){ Q.push(w); //对于每个和u相邻的元素w，如果其尚未访问，则入队列Q } } } |
通过观察宽度优先搜索可以发现，因为 visit 数组的存在，每个点最多只会进入队列一次，因此，遍历图的过程实质上是对每个顶点查找相邻点的过程。其时间复杂度则取决于对应的存储结构。若使用邻接矩阵，那么算法所需时间为 O(n^2) ，而当以邻接表作为图的存储结构时，所需时间为 O(n+e) 。
3.6.3 深度优先搜索（DFS）
深度优先搜索（Depth First Search, DFS）是和宽度优先搜索很相似的一种算法。由于深度优先搜索一般都是用递归来完成，因此其代码长度更加短小，在比赛中更受到青睐，一些普通的搜索题也常常采用深度优先搜索的方式来完成。递归的使用常常使得代码出错的可能性加大，如果不能很好地理解搜索方式，及时停止递归，反而会造成不必要的麻烦。
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。
假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点 v 出发，访问此节点，然后以此从 v 的未被访问的邻接点出发深度优先遍历此图，直至图中所有和 v 路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。
依然以之前的无向图为例，进行图的深度优先搜索。假设从顶点 1 出发进行搜索，在访问了顶点 1 之后，选择邻接点 2 。因为 2 未被访问，则从 2 出发进行搜索。以此类推，接着从 4、8、5 出发进行搜索。在访问了 5 之后，由于 5 的所有邻接点都已被访问，则搜索回到 8 。由于同样的理由，搜索继续回到 4、2 直至 1 ，由于此时 1 的另一个邻接点未被访问，则搜索又从 1 到 3 ，再继续进行下去。由此，得到的顶点访问序列为：
1→2→4→8→5→3→6→7
显然，深度优先搜索是一个递归的过程。为了判断在遍历过程中每个点是否都被访问过，需要设定 visit[maxn] 数组来记录该顶点是否已被访问。
从图的某一顶点 v 出发，递归地进行深度优先遍历的伪代码如下：
|
1 2 3 4 5 6 7 8 |
void DFS(node v){ //从第v个顶点出发递归地深度优先遍历 visit[v]=true; //具体函数内容 //对于每个和v相邻的点w if(!visit[w]) DFS(w); //对v的尚未访问的邻接点w递归调用DFS } |
从上述算法中可以看到，在遍历时，对图中每个点最多只会DFS一次，因为一旦某个点被标记成已被访问，就不再从这个点出发进行搜索。因此，深度优先搜索遍历图的时间复杂度和宽度优先搜索遍历相同，二者不同之处仅在于对顶点访问的顺序不同。而在写法上，DFS不需要BFS所用的队列，而是依托递归实现，代码简短，更适合在比赛时使用，以提高做题的速度。
3.6.4 剪枝
在上图中，假设 1 是起点，搜索时首先会往 2 的方向进行搜索，直到 2 号顶点的所有子结点都搜索完才回溯到 1 号顶点并开始搜索 3 号顶点及其子结点，如果 7 号顶点是解，那么无疑这个解将会最后被发现。而如果有办法在开始的时候就知道 2 号顶点及其子结点不存在答案，那么就可以直接搜素 3 号顶点并更快的找到解。这就是剪枝的概念，即通过预先判断，放弃搜索不可能是解的顶点，来达到节省时间的目的。
剪枝的策略在不同的题目中会有很大的差异，因此无法找到一个通用的模板来描述剪枝的具体过程，但是也有几种剪枝方法是常见的，比如：
（1）可行性剪枝。
（2）最优性剪枝。
（3）交换搜索顺序。
可行性剪枝即目前所处状态已经不满足题目的某些要求，并且其子结点也一定不满足要求的话，就不再对这个结点的子树进行搜索，因为此时搜索出来的状态都一定不是解。
最优性剪枝即当目前所搜索到的结点的后续最优情况也不比当前的最优解好，就停止对当前结点的搜索，回溯到其父亲结点，搜索其他情况。因为此时该结点无论之后会到达何种状态都不会影响最后正解，所以继续搜索其子树是无意义的。
交换搜索顺序严格来说并不是一种剪枝策略，而是一种对搜索方式的优化，即在搜索的时候，改变其搜索的顺序，比如原先是从小到大的顺序，可以换成从大到小，这样可能会减少搜索的总状态，进而加快搜索的效率。即在搜索的时候，有选择的挑选分支小的子树优先搜索。
需要注意的是，剪枝策略必须是保证正确的，否则有可能会出现把正解剪掉这种情况。