算法合集之数据关系的简化

长沙雅礼中学长沙雅礼中学 何林何林常用的数据关系：线性序列，树，图常用的数据关系：线性序列，树，图1243651(1,1)2(2,1)4(3,1)3(4,4)5(5,4)6(6,4)12345781 2 4 2 5 8 5 2 7 2 1 3 1坐船问题 雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。学校希望每个同学都坐上船，同时学校想要租用最少的船。请问：学校至少要租多少船？伍昱伍平何林何刚黄刚何凡伍昱伍平黄刚何刚何林何凡伍昱伍平黄刚何刚何林何凡最优解伍昱伍平黄刚何刚何林何凡一个包含n个点的无向图同名或者同姓的人之间连一条边最小边覆盖伍昱伍平何林何刚黄刚何凡伍昱伍平黄刚何刚何林何凡一片森林每个节点和左孩子同姓每个节点和右孩子同名首先假设所有人是一个连通图黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师首先假设所有人是一个连通图雷锋雷涛黄黄涛欧阳锋黄黄嘎张嘎雷震子黄黄药师周涛黄黄刚张药师没有左儿子了首先假设所有人是一个连通图雷锋雷涛黄黄涛欧阳锋黄黄嘎张嘎雷震子黄黄药师周涛黄黄刚张药师首先假设所有人是一个连通图黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师欧阳涛首先假设所有人是一个连通图黄刚雷锋雷涛涛黄涛涛欧阳锋黄嘎张嘎雷震子黄药师周涛涛张药师欧阳涛涛没有右儿子首先假设所有人是一个连通图黄刚雷锋雷涛涛黄涛涛欧阳锋黄嘎张嘎雷震子黄药师周涛涛张药师欧阳涛涛黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛张药师欧阳涛分析叶子节点独子！黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师周涛周涛张药师欧阳涛欧阳涛独子的情况他们坐一条船剩下的树依然是连通的黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师张药师分析叶子节点落单！树不连通！不是独子黄刚雷锋雷涛黄涛欧阳锋黄嘎张嘎雷震子黄药师张药师分析叶子节点非独子的情况w每次让两个人坐上一条船w树始终保持连通w假设树中有n个点，(n+1)/2条船即可容纳所有人。w这无疑是最优解。w设森林中有m棵树，所有树的规模是n1,n2,nm。w对每棵树分别处理。w答案是(i=1.m)(ni+1)/2伍昱伍平黄刚何刚何林何凡伍昱伍平黄刚何刚何林何凡O(n2)或O(n3)的时间复杂度编程复杂度很高O(n)的时间复杂度编程复杂度很低树的统计一棵树含有n个节点。节点编号为1,2,3,n。定义t(v)为v的后代中所有编号小于v的节点个数。求t(1),t(2),t(3),t(n)。710193411685151221413t(9)=3t(10)=1t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 1 6 0 3 1 0 0 0 2 0对每个点，逐个检查其后代。时间复杂度O(n2)。当n=30000就不可承受。如何把这个“先后”顺序表现出来呢710193411685151221413一个序列中元素之间的先后关系十分明显710142131911658315124710193411685151221413一个序列中元素之间的先后关系十分明显710142131911658315124对应后代多出来的部分9710193411685151221413逆序DFS遍历710 142131911658315124710193411685151221413对应后代多出来的部分9710 1421319116583151247101934116851512214137 10 14 2 13 1 9 11 6 5 8 3 15 12 47 4 3 12 15 9 6 8 5 11 1 10 14 13 2DFS遍历遍历逆逆DFS遍历遍历7101934116851512214137 10 14 2 13 1 9 11 6 5 8 3 15 12 47 4 3 12 15 9 6 8 5 11 1 10 14 13 2DFS遍历遍历逆逆DFS遍历遍历后代！后代！7101934116851512214137 10 14 2 13 1 9 11 6 5 8 3 15 12 47 4 3 12 15 9 6 8 5 11 1 10 14 13 2DFS遍历遍历逆逆DFS遍历遍历9的直系祖先的直系祖先7101934116851512214137 10 14 2 13 1 9 11 6 5 8 3 15 12 47 4 3 12 15 9 6 8 5 11 1 10 14 13 2DFS遍历遍历逆逆DFS遍历遍历红：红：DFS序列中节点序列中节点v后比他小的数的个数后比他小的数的个数蓝：逆蓝：逆DFS序列中节点序列中节点v后比他小的数的个后比他小的数的个数数黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数全部：全部：v-1红：红：DFS序列中节点序列中节点v后比他小的数的个数后比他小的数的个数蓝：逆蓝：逆DFS序列中节点序列中节点v后比他小的数的个后比他小的数的个数数黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数全部：全部：v-1红：红：DFS序列中节点序列中节点v后比他小的数的个数后比他小的数的个数问题：已知一个序列问题：已知一个序列(DFS序列序列)，求每个数后面有多少个数比他小。，求每个数后面有多少个数比他小。解答：用线段树即时更新。时间复杂度解答：用线段树即时更新。时间复杂度O(nlogn)。树简化成线性结构后带来树简化成线性结构后带来的的“序序”关系关系红：红：DFS序列中节点序列中节点v后比他小的数的个数后比他小的数的个数蓝：逆蓝：逆DFS序列中节点序列中节点v后比他小的数的个后比他小的数的个数数黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数全部：全部：v-1蓝：逆蓝：逆DFS序列中节点序列中节点v后比他小的数的个后比他小的数的个数数问题：已知一个序列问题：已知一个序列(逆逆DFS序列序列)，求每个数后面有多少个数比他小。，求每个数后面有多少个数比他小。解答：用线段树即时更新。时间复杂度解答：用线段树即时更新。时间复杂度O(nlogn)。树简化成线性结构后带来树简化成线性结构后带来的的“序序”关系关系红：红：DFS序列中节点序列中节点v后比他小的数的个数后比他小的数的个数蓝：逆蓝：逆DFS序列中节点序列中节点v后比他小的数的个后比他小的数的个数数黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数全部：全部：v-1黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数7101934116851521413黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 107黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 147 107黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 27 10 147 107黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 137 10 14 27 10 147 107黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 137 10 14 27 10 147 1077 1黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 137 10 14 27 10 147 1077 17 9黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 137 10 14 27 10 147 1077 17 97 9 11黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 137 10 14 27 10 147 1077 17 97 9 117 9 6黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 137 10 14 27 10 147 1077 17 97 9 117 9 67 9 6 5黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数71019341168515214137 10 14 137 10 14 27 10 147 1077 17 97 9 117 9 67 9 6 513的直系祖先的直系祖先5的直系祖先的直系祖先深度优先搜索中要用到一个栈来存储节点（比如递归）。深度优先搜索中要用到一个栈来存储节点（比如递归）。任意时刻，栈顶元素的直系祖先就是栈中其余的节点。任意时刻，栈顶元素的直系祖先就是栈中其余的节点。用一棵线段树来维护这个栈。求每个节点的直系祖先中有用一棵线段树来维护这个栈。求每个节点的直系祖先中有多少个比他本身小就能用多少个比他本身小就能用O(nlogn)的时间复杂度实现。的时间复杂度实现。红：红：DFS序列中节点序列中节点v后比他小的数的个数后比他小的数的个数蓝：逆蓝：逆DFS序列中节点序列中节点v后比他小的数的个后比他小的数的个数数黄：黄：v的直系祖先中比的直系祖先中比v小的节点个数小的节点个数全部：全部：v-1综合上面的分析，红、蓝、黄我们都能在综合上面的分析，红、蓝、黄我们都能在O(nlogn)的时间复杂的时间复杂度内求出。所以整个问题解决，时间复杂度是度内求出。所以整个问题解决，时间复杂度是O(nlogn)。7101934116851512214137 10 14 2 13 1 9 11 6 5 8 3 15 12 47 4 3 12 15 9 6 8 5 11 1 10 14 13 2DFS遍历遍历逆逆DFS遍历遍历9的直系祖先的直系祖先w图树，树序列。w有时候不需要包罗万象的所有信息w合理的组织数据之间的关系w利用简化数据关系实现数据的有序化w简化后的关系更明了，有利于窥见本质矛盾。