当前位置:首页 >> 学科竞赛 >>

省夏令营讲稿


基本算法
陈乐群 (abcdabcd987)
上海交通大学 / 泉州市第七中学

基本算法
? ? ? ?

函数的增?长(科普) 贪?心 分治 ?二分

函数的增?长(科普)

函数的增?长:Θ符号
c2g(n)
?

如果

存在三个正常数 n0, c1, c2,使得对于任意的 n>n0 都有 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) ,那 么称函数 f(n) ∈ Θ(g(n)) 但是正常来说,由于 Θ 和 O ?长得很像,并且 O 便于输?入和 朗读,所以经常会?用 O 符号指 代 Θ 符号 n0

f(n)

c1g(n)

?

n

函数的增?长:插?入排序
代码 INSERTION-SORT(A): for j = 2 to A.length: key = A[j] i = j-1 while i > 0 and A[i] > key: A[i+1] = A[i] i = i-1 A[i+1] = key c c c c c c c n n-1 n-1 Σ Σ Σ n-1 代价 次数

最坏情况下,Σtj = ?n(n+1) -1 ,对上述代价*次数求和得到:运?行时间 T(n) = (?c4+?c5+?c6)n2 + (c1+c2+c3+?c4-?c5-?c6+c7)n - (c2+c3+c4+c7)

T(n) ∈ Θ(n2)

贪?心

贪?心:以动态规划为基础
1. 确定问题的最优?子结构 2. 设计?一个递归算法 3. 证明如果我们做出?一个贪?心的选择,那么只剩下 ?一个?子问题 4. 证明贪?心选择总是安全的 5. 设计?一个新的递归算法实现贪?心策略 6. 将递归算法改为迭代算法

贪?心:以直觉为基础
1. 每次选择当前的最优策略,以此设计算法 2. 检验是否符合最优?子结构 3. 打代码 4. AC 5. 证明贪?心是正确的

贪?心:最优?子结构

?

如果?一个问题的最优解包含了其?子问题的最优解, 称此问题具有最优子结构性质。 贪?心和动态规划都需要?用到最优?子结构性质。

?

NOIP2012 提?高组:均分纸牌
? ? ? ?

有 N 堆纸牌排成?一列,编号为 1, 2, ..., N 第 i 堆纸牌有 a[i] 张牌 纸牌总数为 N 的倍数 每次可以从某?一堆纸牌中抽取若干张,然后移动 到相邻的那堆纸牌中 问最少需要多少次移动才能够使得每堆纸牌的数 量相等?

?

NOIP2012 提?高组:均分纸牌
?

假设 N 堆纸牌共有 M 张纸牌,那么均分完了之 后,每堆纸牌中的纸牌数 x = M / N 从第 1 堆到第 N-1 堆:
? ? ?

?

如果 a[i] > x :从第 i 堆移动 a[i]-x 张牌到第 i+1 堆 如果 a[i] = x :不移动 如果 a[i] < x :从第 i+1 堆移动 a[i]-x 张牌到第 i 堆

?

如果前 N-1 堆都达到了 x ,那么第 N 堆也达到了 x。

NOIP2012 提?高组:均分纸牌
N=5, M=30, x=6 a[1] 2 6 6 a[2] 4 0 6 a[3] 1 1 -5 a[4] 13 13 13 a[5] 10 10 10

出现了负数?

NOIP2012 提?高组:均分纸牌
N=5, M=30, x=6 a[1] a[2] a[3] a[4] a[5] 2 6 6 6 6 4 0 6 6 6 1 1 -5 6 6 13 13 13 2 6 10 10 10 10 6 2 6 6 6 6 4 0 0 6 6 等同于 a[1] a[2] a[3] a[4] a[5] 1 1 12 6 6 13 13 2 2 6 10 10 10 10 6

? ? ?

负数并不影响结果的正确性 等同于在出现负数之前的某?一步中,先将右边的 牌向左移动到原本会出现负数的那堆牌中 总存在合法?方案

区间覆盖问题
? ? ?

给定?一个?长度为 M 的数轴 有 N 条线段,左右端点分别是 L[i] 和 R[i] 求?至少要?用?几条线段才能完全覆盖这个数轴

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题
? ?

每次选择左端点 在当期已覆盖区域中 且 最右端点 最靠右的线段进?行覆盖 做之前可以先按左端点递增排序,以降低复杂度

1

2

3

4

5

6

7

8

区间覆盖问题:证明
? ? ? ? ?

假设到了当前这次决策前,我们已经?用这个?方法得到了??目前的最优解 要保证数轴被完整覆盖,必须选取左端点在已覆盖区间内的线段 对于上述合法线段,我们肯定是要让覆盖的区域尽量?大,所以我们选择右端点最远 的线段;其余的合法线段?一定会被这条线段覆盖,所以不如这条线段优 这样,这次决策也拿到了最优解 这样?一来,只要选的第?一条线段是最优的,按照这个过程就会得到全局的最优解

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

给定?一个?长度为 M 的数轴 有 N 条线段,左右端点分别是 L[i] 和 R[i] 求?至多可以选取?几条线段使得它们互不重叠?

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2
? ? ?

按右端点升序排序 对于右端点相同的?几条线段,保留左端点最靠右的;其余的丢掉 按顺序处理,如果当前这条加进去不会与之前的重叠,那么就加 进去;否则就丢掉这条

1

2

3

4

5

6

7

8

区间覆盖问题2:证明
?

显然对于同?一个右端点,左端点靠右的?比较优

? ?

当前线段如果能塞得进去那就塞进去,因为此时它不会挡住任何合 法线段(它们都在当前线段塞进去前塞进去了) 塞不进去就丢掉。硬塞可能会导致更劣;并且丢掉的话,给后?面线 段留下的空间也?比较?大

1

2

3

4

5

6

7

8

分治

分治
?

在分治策略中,我们递归地求解?一个问题,在每 层递归中应?用如下三个步骤:
?

分解:将问题划分为?一些?子问题。?子问题的形 式与原问题?一样,只是规模更?小 解决:递归地求解出?子问题。如果?子问题的规 模?足够?小,则停?止递归,直接求解 合并:将?子问题的解组合成原问题的解

?

?

快速幂

?

最简单的例?子:在 O(log n) 的时间内求出 an

快速幂
?

划分:
? ?

如果 n 为偶数,那么 an = an/2 × an/2 如果 n 为奇数,那么 an = a(n-1)/2 × a(n-1)/2 × a

?

解决:
? ?

如果 n = 0 ,那么 an = 1 如果 n ≠ 0 ,那么递归解决
其实?一般来说合并都是?比较简单的 重点在于如何划分和解决

?

合并:
?

同划分

快速幂
?

当然,正确的实现也很重要

POWER(a, n): if n == 0: return 1 if n mod 2 == 0: return POWER(a, n div 2) * POWER(a, n div 2) else: return POWER(a, n div 2) * POWER(a, n div 2) * a

O(n) !

快速幂
?

当然,正确的实现也很重要

POWER(a, n): if n == 0: return 1 tmp = POWER(a, n div 2) if n mod 2 == 0: return tmp * tmp else: return tmp * tmp * a

O(log n)

快速幂
?

当然,正确的实现也很重要
POWER(a, n): ans = 1 while n ≠ 0: if n&1 == 1: ans = ans * a a = a * a n = n div 2 return ans

POWER(a, n): if n == 0: return 1 tmp = POWER(a, n div 2) if n mod 2 == 0: return tmp * tmp else: return tmp * tmp * a

有的分治算法可以轻松地转成?非递归实现

快速排序
?

?一个??广为流传的快排程序 (pascal) :
procedure qsort(l,r:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a[(l+r)div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end;

快速排序
? ?

把数组 A[p..r] 进?行快速排序 分解:确定?一个基准元素 A[q] ,把 A[p..r] 划分成两个 ?子数组 A[p..q-1] 和 A[q+1..r] ,使得左边这组的所有元 素都?小于 A[q] ,并且右边那组的所有元素都?大于 A[q] 解决:递归处理左右两个?子数组
左右两边不要求有序

? ?

合并:因为是直接在原数组上进?行操作,所以解决完成 后,A[p..r] 已经有序,?无须合并
?又是打酱油

快速排序:确定基准
?

基准 A[q] :所有?比 A[q] ?小的都要扔到左边,?比 A[q] ?大的都 要扔到右边。 如果不幸每次操作选取的基准都是当前范围内最?小的数呢? 基准的选择决定快排的时间! 第?一个元素 或者 最后?一个元素 中间元素 1/3元素 随机元素

? ? × ? ? ?

快速排序:Demo
6
i

3

7

5

8

4

2

1
j

快速排序:Demo
6
i

3

7

5

8

4

2

1
j

快速排序:Demo
1 3
i

7

5

8

4

2
j

6

快速排序:Demo
1 3 2 5
i

8

4
j

7

6

快速排序:Demo
1 3 2 4 8
ij

5

7

6

快速排序:Demo
1 3 2 4 8 8 5 5 7 7 6 6

快速排序:Demo
1 3 2 4 8 8 5 5 7 7 6 6

快速排序:Demo
1 3 2 4 8 5 5 8 7 7 6 6

快速排序:Demo
1 3 2 4 8 5 5 8 8 7 7 7 6 6 6

快速排序:Demo
1 3 2 4 8 5 5 8 8 7 7 7 6 6 6

快速排序:Demo
1 3 2 4 8 5 5 8 6 7 7 7 6 6 8

快速排序:Demo
1 3 2 4 8 5 5 8 6 7 7 7 6 6 8 8

快速排序:Demo
1 3 2 4 8 5 5 8 6 7 7 7 6 6 8 8

快速排序:Demo
1 3 2 4 8 5 5 8 6 …… 1 2 3 4 5 6 7 8 7 7 7 6 6 8 8

快速排序
?

?一个??广为流传的快排程序 (pascal) :
procedure qsort(l,r:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a[(l+r)div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end;

快速排序
?

?一个??广为流传的快排程序 (pascal) :
procedure qsort(l,r:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a[(l+r)div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end;

选择基准元素

快速排序
?

?一个??广为流传的快排程序 (pascal) :
procedure qsort(l,r:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a[(l+r)div 2]; 选择基准元素 repeat while a[i]<x do inc(i); 找到?一个不应该出现在左侧的元素 while a[j]>x do dec(j); 和?一个不应该出现在右侧的元素 if i<=j then begin 交换它们 t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end;

抗-快速排序
?

已知某选?手的快排程序如上(基准取中间),请 你设计?一个程序?生成?一组输?入数据,使得它被卡 出翔 亦即使它的快排退化到 O(n2) 复杂度

?

?心理不健康的出题?人!

抗-快速排序

?

要让快排变成 O(n2) 的算法,就要让每?一次递归 的时候,把递归区间分成?大?小为 0 和 n-1 的两块 也就是每次的基准都是最?小的元素!

?

抗-快速排序
1 qsort[1..8] A 2 B 3 C 4 D 5 E 6 F 7 G 8 H

抗-快速排序
1 qsort[1..8] A 2 B 3 C 4 D 5 E 6 F 7 G 8 H

i

O(n)

j

抗-快速排序
1 qsort[1..8] qsort[2..8] D D 2 B B 3 C C 4 A A 5 E E 6 F F 7 G G 8 H H

抗-快速排序
1 qsort[1..8] qsort[2..8] D D 2 B B 3 C C 4 A A 5 E E 6 F F 7 G G 8 H H

抗-快速排序
1 qsort[1..8] qsort[2..8] qsort[3..8] D D D 2 B E E 3 C C C 4 A A A 5 E B B 6 F F F 7 G G G 8 H H H

抗-快速排序
1 qsort[1..8] qsort[2..8] qsort[3..8] D D D 2 B E E 3 C C C 4 A A A 5 E B B 6 F F F 7 G G G 8 H H H

抗-快速排序
1 qsort[1..8] qsort[2..8] qsort[3..8] qsort[4..8] D D D D 2 B E E E 3 C C B B 4 A A A A 5 E B C C 6 F F F F 7 G G G G 8 H H H H

抗-快速排序
1 qsort[1..8] qsort[2..8] qsort[3..8] qsort[4..8] D D D D 2 B E E E 3 C C B B 4 A A A A 5 E B C C 6 F F F F 7 G G G G 8 H H H H

抗-快速排序
1 qsort[1..8] qsort[2..8] qsort[3..8] qsort[4..8] D D D D 2 B E E E 3 C C B B 4 A A A F 5 E B C C 6 F F F A 7 G G G G 8 H H H H



抗-快速排序
1 qsort[1..8] qsort[2..8] qsort[3..8] qsort[4..8] D D D D 2 B E E E 3 C C B B 4 A A A F 5 E B C C 6 F F F A 7 G G G G 8 H H H H


qsort[8..8] D E B F A G C H

抗-快速排序
1 qsort[1..8] qsort[2..8] qsort[3..8] qsort[4..8] D D D D 2 B E E E 3 C C B B 4 A A A F 5 E B C C 6 F F F A 7 G G G G 8 H H H H


qsort[8..8] D E B F A G C H

O(n)

抗-快速排序

1 D

2 E

3 B

4 F

5 A

6 G

7 C

8 H

抗-快速排序

O(n )
5 A 3 B 7 C 1 D 2 E 4 F 6 G 8 H

2

抗-快速排序
ANTI-QSORT(N): for i = 1 to N: id[i] = i for i = 1 to N: swap(id[i], id[(i+N)/2]) for i = 1 to N: a[id[i]] = i return a

第 k ?小查询
? ? ? ?

给定?一个数组,查询其中的第 k ?小元素 复杂度 O(n) 允许打乱数组 快排?

第 k ?小查询
? ?

只要第 k ?小,所以就不?用全部排序了 第 k ?小那个数,在每次递归中,必然属于左半边 或者右半边 因此我们只要看第 k ?小的数在哪边就好了

?

第 k ?小查询
?

快排
procedure qsort(l,r:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a[(l+r)div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if (i<r) then qsort(i,r); if (l<j) then qsort(l,j); end;

第 k ?小查询
?

基本和快排没区别
procedure qsort(l,r:longint); var i,j,x,t:longint; begin i:=l;j:=r;x:=a[(l+r)div 2]; repeat while a[i]<x do inc(i); while a[j]>x do dec(j); if i<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if (i<r)and(k>=i) then qsort(i,r); if (l<j)and(k<=j) then qsort(l,j); end;

归并排序

?

简单粗暴的分治!

归并排序
?

分解:把?长度为 n 的序列分成左右两半?长度为 n/2 的?子序列 解决:分别递归排序两个?子序列 合并:把左右两个已有序的?子序列合并

? ?

归并排序
?

分解:把?长度为 n 的序列分成 左右两半?长度为 n/2 的?子序列 解决:分别递归排序两个?子序 列 合并:把左右两个已有序的?子 序列合并

?

MERGE-SORT(A, lef, rig): if lef == rig: return mid = (lef+rig)/2 MERGE-SORT(A, lef, mid) MERGE-SORT(A, mid+1, rig) MERGE(A[lef..mid], A[mid+1,rig])

?

归并排序:复杂度分析
MERGE-SORT[1..16] MERGE-SORT[1..8] MERGE-SORT[9..16] [1..4] [5..8] [9..12] [13..16] O(n) O(n) O(n) O(n) O(n)

O(nlogn)
O(logn)

归并排序:合并有序序列
? ? ? ?

两个序列都有序 我们分别?用两个指针指向这两个序列 每次?比较两个指针指向的数,把?比较?小的先拿出来 如果有?一个指针达到了尽头,那么全部取另?一个指针

归并排序:合并有序序列
MERGE(A[lef..mid], A[mid+1..rig]): i = lef, j = rig, k = lef L[lef..mid] = A[lef..mid] R[mid+1..rig] = A[mid+1..rig] L[mid+1] = ∞, R[rig+1] = ∞ while k < rig: if L[i] ≤ R[j]: A[k] = L[i] ++i, ++k else: A[k] = R[j] ++j, ++k

归并排序:合并有序序列
MERGE(A[lef..mid], A[mid+1..rig]): i = lef, j = rig, k = lef L[lef..mid] = A[lef..mid] R[mid+1..rig] = A[mid+1..rig] L[mid+1] = ∞, R[rig+1] = ∞ while k < rig: if L[i] ≤ R[j]: A[k] = L[i] ++i, ++k else: A[k] = R[j] ++j, ++k 三个指针

归并排序:合并有序序列
MERGE(A[lef..mid], A[mid+1..rig]): i = lef, j = rig, k = lef L[lef..mid] = A[lef..mid] R[mid+1..rig] = A[mid+1..rig] L[mid+1] = ∞, R[rig+1] = ∞ while k < rig: if L[i] ≤ R[j]: A[k] = L[i] ++i, ++k else: A[k] = R[j] ++j, ++k 三个指针 将左右两边复制到临时数组

归并排序:合并有序序列
MERGE(A[lef..mid], A[mid+1..rig]): i = lef, j = rig, k = lef L[lef..mid] = A[lef..mid] R[mid+1..rig] = A[mid+1..rig] L[mid+1] = ∞, R[rig+1] = ∞ while k < rig: if L[i] ≤ R[j]: A[k] = L[i] ++i, ++k else: A[k] = R[j] ++j, ++k 三个指针 将左右两边复制到临时数组 在最后?面放上取不到的最?大值

归并排序:合并有序序列
MERGE(A[lef..mid], A[mid+1..rig]): i = lef, j = rig, k = lef L[lef..mid] = A[lef..mid] R[mid+1..rig] = A[mid+1..rig] L[mid+1] = ∞, R[rig+1] = ∞ while k < rig: if L[i] ≤ R[j]: A[k] = L[i] ++i, ++k else: A[k] = R[j] ++j, ++k 三个指针 将左右两边复制到临时数组 在最后?面放上取不到的最?大值

?一个?一个合并到 A 数组中

逆序对

? ?

给定序列 A[i] 求有多少对 (i, j) 满?足 i < j 并且 A[i] > A[j]

逆序对
? ? ? ? ? ?

归并排序? 分治的常规思路: 分两半 递归左边 递归右边 合并两边

INVERSION(A, lef, rig): mid = (lef+rig)/2 anslef = INVERSION(A, lef, mid) ansrig = INVERSION(A, mid+1, rig) return anslef + ansrig ???

逆序对
?

考虑?一对逆序对的两个数:
!

INVERSION(A, lef, rig): mid = (lef+rig)/2 anslef = INVERSION(A, lef, mid) ansrig = INVERSION(A, mid+1, rig) return anslef + ansrig ???

?

要么这两个数同在左边 要么这两个数同在右边 要么这两个数一左一右

?

?

逆序对
?

考虑?一对逆序对的两个数:
!

?

要么这两个数同在左边 要么这两个数同在右边 要么这两个数一左一右

INVERSION(A, lef, rig): mid = (lef+rig)/2 anslef = INVERSION(A, lef, mid) ansrig = INVERSION(A, mid+1, rig) anscross = MERGE(A, lef, mid, rig) return anslef + ansrig + anscross

?

?

逆序对
? ? ?

现在我们考虑?一左?一右的情况 分别处理完左右两边之后,左右两边都是有序的 那么?一左?一右的情况就是:左半边的任何?一个数 与 右半边任何?一个?比它?小的数 都能够组成逆序对 这个可以?非常轻松地在合并的时候完成 即当右半边的某个数归?入原数组时,答案加上此 时左半边已经归?入原数组的个数

? ?

逆序对
A[1..5]

1 i

4

5

6

8

A[6..10]

2 j

3

5

7

9

ans = 0
A[1..10]

逆序对
A[1..5]

4 i

5

6

8

A[6..10]

2 j

3

5

7

9

ans = 0
A[1..10] 1

逆序对
A[1..5]

4 i

5

6

8

A[6..10]

3 j

5

7

9

1 1 ans = +

A[1..10] 1

2

逆序对
A[1..5]

4 i

5

6

8

A[6..10]

5 j

7

9

1 2 ans = +

A[1..10] 1

2

3

逆序对
A[1..5]

5 i

6

8

A[6..10]

5 j

7

9

ans = 2
A[1..10] 1

2

3

4

逆序对
A[1..5]

5 i

6

8

A[6..10]

7 j

9

ans = 2
A[1..10] 1

2

3

4

5

逆序对
A[1..5]

6 i

8

A[6..10]

7 j

9

2 4 ans = +

A[1..10] 1

2

3

4

5

5

?二分

?二分
?

常?见?用法:
!

? ? ?

查找函数零点 ?二分查找 ?二分答案再进?行处理

查找函数零点
f(x)
?

在区间 (a, b) 上 f(x) 有单调性 若有 f(a)f(b) < 0 那么?方程 f(x) = 0 在区间 (a, b) 上?至少有?一个根
f(a)>0 b a f(b)<0

?

?

x

查找函数零点
?

实数?二分,?比较简单,注意控制精度

double lef = a, rig = b; while (rig-lef > 1e-6) { double mid = (lef+rig)/2; if (f(lef)*f(mid) < 0) rig = mid; else lef = mid; }

查找函数零点
?

实数?二分,?比较简单,注意控制精度

double lef = a, rig = b; while (rig-lef > 1e-6) { double mid = (lef+rig)/2; if (f(lef)*f(mid) < 0) rig = mid; else lef = mid; }

控制精度

查找函数零点
?

实数?二分,?比较简单,注意控制精度

double lef = a, rig = b; while (rig-lef > 1e-6) { double mid = (lef+rig)/2; if (f(lef)*f(mid) < 0) rig = mid; else lef = mid; }

控制精度

零点在区间 (lef, mid) 之间

?二分查找

? ?

给定?一个有序数列,查找其中符合某个要求的数 复杂度 O(log n)

?二分查找
? ? ?

给定?一个不降序数列 arr 和?一个数 value 查找?一个最?大的 i 使得 arr[i] == value 不存在返回 -1

?二分查找
FIND_LAST_MATCH(arr, value): lef = 1, rig = n+1 while rig-lef > 1: mid = (lef+rig)/2 if arr[mid] < value: lef = mid else: rig = mid ! if arr[lef] == value: return lef else: return -1

?二分查找
FIND_LAST_MATCH(arr, value): lef = 1, rig = n+1 while rig-lef > 1: mid = (lef+rig)/2 if arr[mid] < value: lef = mid else: rig = mid ! if arr[lef] == value: return lef else: return -1 ?二分区间为 [lef, rig)

?二分查找
FIND_LAST_MATCH(arr, value): lef = 1, rig = n+1 while rig-lef > 1: mid = (lef+rig)/2 if arr[mid] < value: lef = mid else: rig = mid ! if arr[lef] == value: return lef else: return -1 ?二分区间为 [lef, rig) 集合中还有?至少2个数

?二分查找
FIND_LAST_MATCH(arr, value): lef = 1, rig = n+1 while rig-lef > 1: mid = (lef+rig)/2 if arr[mid] < value: lef = mid else: rig = mid ! if arr[lef] == value: return lef else: return -1 ?二分区间为 [lef, rig) 集合中还有?至少2个数

lef 保存有可能是答案的数

?二分查找
FIND_LAST_MATCH(arr, value): lef = 1, rig = n+1 while rig-lef > 1: mid = (lef+rig)/2 if arr[mid] < value: lef = mid else: rig = mid ! if arr[lef] == value: return lef else: return -1 ?二分区间为 [lef, rig) 集合中还有?至少2个数

lef 保存有可能是答案的数 rig 保存永远不可能取到的数

?二分查找
FIND_LAST_MATCH(arr, value): lef = 1, rig = n+1 while rig-lef > 1: mid = (lef+rig)/2 if arr[mid] < value: lef = mid else: rig = mid ! if arr[lef] == value: return lef else: return -1 ?二分区间为 [lef, rig) 集合中还有?至少2个数

lef 保存有可能是答案的数 rig 保存永远不可能取到的数

最后的答案就是 lef

?二分查找
FIND_LAST_MATCH(arr, value): lef = 1, rig = n+1 while rig-lef > 1: mid = (lef+rig)/2 if arr[mid] <= value: lef = mid else: rig = mid ! if arr[lef] == value: return lef else: return -1 ?二分区间为 [lef, rig) 集合中还有?至少2个数

lef 保存有可能是答案的数 rig 保存永远不可能取到的数

最后的答案就是 lef 还要考虑 -1 的情况

?二分查找

?

?二分查找很好写?

I’ve assigned this problem in courses at Bell Labs and IBM. Professional programmers had a couple of hours to convert the above description into a program in the language of their choice; a high-level pseudocode was ?ne. At the end of the speci?ed time, almost all the programmers reported that they had correct code for the task. We would then take thirty minutes to examine there code, which the programmers did with test cases. In several classes and with over a hundred programmers, the result varied little: ninety percent of the programmers found bugs in their programs (and I wasn’t always convinced of the correctness of the code in which no bugs were found). –Page 36, Programming Pearls

“任何简单的问题认真起来就不再简单。很多 让微软和其他公司遭受巨大损失的安全漏洞, 就是源于一些看似都不错,其实有漏洞的边界 条件检查。”
–《编程之美》第261?页

?二分查找
? ? ? ? ? ? ? ?

给定?一个不降序数列 arr 和?一个数 value,查询符合下列要求的 i 任?一个 i 使得 arr[i] = value 最?小的 i 使得 arr[i] = value 最?大的 i 使得 arr[i] = value 最?大的 i 使得 arr[i] < value 最?小的 i 使得 arr[i] > value 最?大的 i 使得 arr[i] ≤ value 最?小的 i 使得 arr[i] ≥ value

?二分查找的正确写法
?

根据前辈们的经验总结?而来,按照这么写?比较不 会错: ?二分区间为 [lef, rig) 或者 (lef, rig] 其中开区间的那个数表?示取不到的 闭区间那个数在?二分过程中表?示候选答案 最后的答案是闭区间的那个数

? ? ? ?

?二分查找的正确写法
区间[lef, rig): ! lef = min, rig = max+1 while (rig-lef > 1): mid = (lef+rig)/2 if valid(mid): lef = mid else: rig = mid ! print lef ! 适?用于找最?大的值 区间(lef, rig]: ! lef = min-1, rig = max while (rig-lef > 1): mid = (lef+rig)/2 if valid(mid): rig = mid else: lef = mid ! print rig ! 适?用于找最?小的值

矩形计数

? ?

给定平?面上的 N(≤5000) 个点 问四个顶点都在这些点上,并且边平?行坐标轴的 矩形有多少个?

矩形计数
枚举左上?角和右下?角这两个点 这样就可以知道另外两个点的坐标 查询这两个点是否在给定的点列表?里?面

? ? ?

矩形计数
? ? ? ?

查询这两个点是否在给定的点列表?里?面 ?二分查找! 可是点不是?二维的吗? 怎么?二分查找?

矩形计数
? ? ? ? ?

?二分查找需要被查找类型?支持<操作符 只要有<操作符即可完成?二分查找 因为 a > b → not (a < b) a = b → not (a < b or b < a)

矩形计数
? ?

有序数对 (x, y) 的?比较:双关键字?比较 先检验第?一个关键字,如果第?一个关键字相同, 再检验第?二关键字 ?比?方说检验 A < B:
return A.x < B.x or (A.x == B.x and A.y < B.y)
C / C++: ! struct Point { int x, y; }; Point A, B;

?
?

Pascal: ! type Point=record x, y:longint; end; var A, B:Point;

矩形计数
?

复杂度 O(n log n + n2log n)
!

? ?

更好的?方法?改?用 hash 的话 O(n2) 更简便的?方法?std::set<Point>

?二分答案再乱搞
? ? ? ?

?二份答案再乱搞类型的题??目?十分多?见 常?见关键字: 求最?大值的最?小 求最?小值的最?大
!

?

注意答案要满?足单调性

序列划分
? ? ?

给定?长度为 n 的序列 a[i] 划分成最多 m 份 如何划分使得每份和的最?大值最?小?
!

? ?

例如如下序列最多划分成3份,每段和的最?大值最?小为 8: 2 1 4 | 5 3 | 6

序列划分
? ? ? ? ?

不好考虑?如果已知答案 ans 呢? 那就变成判定性问题: 给定?长度为 n 的序列 a[i] 划分成若干份,每份的和最?大不能超过 ans 问最少需要划分成?几份?

序列划分

? ?

贪?心! 每?一份包含尽可能多的数,直到超出 ans

序列划分
?

枚举?一个答案 ans ,检查每段和最?大为 ans ?至少 要划分成多少份,如果不多于 m 那么就是合法的 从?小到?大枚举答案? ?二分答案? 注意到,如果?一个答案 ans 是合法的,那么答案 ans+1 也必然是合法的,即有单调性 ?二分!

? ? ?

?

序列划分
lef = -1, rig = Σa[i] while (rig-lef > 1): mid = (lef+rig)/2 if check(mid) ≤ m: rig = mid else: lef = mid ! print lef

序列划分
lef = -1, rig = Σa[i] while (rig-lef > 1): mid = (lef+rig)/2 if check(mid) ≤ m: rig = mid else: lef = mid ! print lef

贪?心 求解在已知每份和不能超过 mid 的情况下 最少要把序列分成多少份

The End Thanks !
My OI Blog: http://quartergeek.com


相关文章:
2015年夏令营讲话稿
2015年夏令营讲话稿_计划/解决方案_实用文档。2015 年夏令营讲话稿 2015 年夏令营讲话稿 各位营员,各位远道而来的青年朋友: 此时此刻, 我代表哲学学院的全体师生...
夏令营发言稿
夏令营发言稿_演讲/主持_工作范文_实用文档。夏令营发言稿敬爱的老师们,亲爱的同学们: 大家下午好! 期盼已久的暑期夏令营活动即将拉开序幕, 我们就要开始丰富多彩的...
夏令营讲话稿2016
夏令营讲话稿2016_演讲/主持_工作范文_实用文档。亲爱的同学们: 大家好! 在...2016山东省数学夏令营获... 26页 1下载券 2016暑期夏令营闭营仪式... 暂无...
夏令营发言稿
为了使本次夏令营活动能圆满成功,我倡议全体营员努力做到以下几点: 1、认真听从...身为省常中分校的常州外国语学校,拥有优秀的教育资源,是全市数千名毕业生向往...
夏令营开营仪式讲话稿
夏令营开营仪式讲话稿_其它_总结/汇报_实用文档。夏令营开营仪式讲话稿各位老师,亲爱的同学们,大家上午好! 结束了一个学期紧张充实的学习生活, 令我们期待和兴奋的...
夏令营发言稿
为了使本次夏令营活动能圆满成功,我倡议全体营员努力做到以下几点: 1、认真听从...身为省常中分校的常州外国语学校,拥有优秀的教育资源,是全市数千名毕 业生...
夏令营讲话稿
夏令营讲话稿_演讲/主持_工作范文_应用文书。夏令营闭营式上代表家长讲话。夏令营发言稿尊敬的各位领导和各位辅导老师、亲爱的同学们: 大家下午好!今天非常容幸代表各...
夏令营代表发言稿
夏令营代表发言稿_演讲/主持_工作范文_实用文档。夏令营代表发言稿 尊敬的领导、老师,亲爱的同学: 大家好!非常荣幸代表全体营员发言,我叫***,来自**大学**专业。...
夏令营演讲稿
我们在此承诺,我们 定将以满腔的热情、最真诚的态度、最出色的的表现为各位营员做好服务工作, 以使此次夏令营活动取得圆满成功。 中国有句古话“读万卷书行万里...
夏令营演讲稿
夏令营讲稿_其它_党团工作_应用文书。今日推荐 157份文档 2015国家公务员考试备战攻略 2015国考行测模拟试题及历年真题 2015国考申论押密试卷及答案 2015国考面试...
更多相关标签:
国际夏令营校长讲话稿 | 省长讲话稿 | 创建省级生态市讲稿 | 省委书记讲话稿 | 省领导讲话稿 | 省 开班仪式讲话稿 | 省委书记任职讲话稿 | 团省委领导讲话稿 |