算法合集之《问题中的变与不变》.ppt

问题中的变与不变,长沙市雅礼中学 陈雪,引言,对变量进行操作是信息学中的常见问题。 如果能找到变量之间的关系，把变量转化成不变量，那么算法的效率就将得到质的提升。,例一蚂蚁,一条树枝上有N只蚂蚁。给出他们的位置，如何安排蚂蚁初始的方向使得全部蚂蚁掉落的时间最早或最晚。 最多1,000,000只蚂蚁。,感性认识,左边的蚂蚁向左端走，右边的蚂蚁向右端走。 如何使全部掉落的时间最晚？ 猜想：让左边的蚂蚁向右端走，同时右边的蚂蚁向左端走。,理性分析,直接证明猜想难度比较大。 看一般的情况: 纪录2只蚂蚁的有用信息:速度 和位置 。 设 。,在蚂蚁相遇前一刻,在蚂蚁相遇后一颗,一个集合内蚂蚁相遇,集合不变,继续分析,另 任何两只属于集合U内的蚂蚁相遇之后，集合U不变。 集合U只随着时间的变化而变化。 Ansi=蚂蚁I按起始方向走到端点,继续分析,回到原问题 最早时间= 最迟时间= 猜想得证！ 最终时间复杂度O( n )。,即左边蚂蚁向左走，右边蚂蚁向右走,Max蚂蚁I向近端出发,Max蚂蚁I向远端出发,即左边蚂蚁向右走，右边蚂蚁向左走,小结,分析题目的特殊特点: 1.原路返回 2.速度相同 将速度变量固定，成为常量。 问题得到了简化。,例二circular way,安排一种方案 使得总代价最小 n50000 最小权匹配！ 无法满足题目要求！ 设A类点顺时针排序的坐标为A1,A2 An 设B类点顺时针排序的坐标为B1,B2 Bn,优化算法,最小权匹配必然满足下面的性质: 通过调整可以得到更优解,两条匹配边不会交叉,算法二,1.枚举和A1匹配的点Bk。 2.然后按顺序一一求出和Ai匹配的点。 3.最后统计当前的代价和，更新答案。,时间复杂度,继续分析,另Ci表示当前Ai与它匹配的Bj的距离。 当前的代价sum=Ci Ci随着我们枚举k而变化。,找出Ci中蕴含的不变？,观察Ci,由于Ai到Bj有顺时针，逆时针2种走法。 Ci =Min|Ai-Bj|,L-|Ai-Bj| Ci只同Ai和Bj有关。 不妨把Ci看成Ai和Bj的函数。 设Ci=f(Ai)+g(Bj),讨论Ci,0,从 顺时针走到,讨论Ci,0,从 逆时针走到,讨论Ci,0,从 顺时针走到,讨论Ci,0,从 逆时针走到,继续分析,根据Ai,Bi的有序性，得到f(Ai)的每种情况对应的Bj都是连续的一段。 f(Ai)在枚举和A1匹配的点Bk的过程中 只会发生4次变化。 从Ci的N次变化 f(Ai),g(Bi)的4次变化,回到原问题,当前的代价sum=Ci=f(Ai)+g(Bi) A1匹配Bk，sum已经求出。 当A1匹配Bk+1，更新f(Ai),g(Bi),sum。 sum=sum-f(Ai)+f(Ai)-g(Bi)+g(Bi) 把一个-f(Ai)+f(Ai)和-g(Bi)+g(Bi) 看成一次事件,f(Ai)表示上一时刻f(Ai) f(Ai)表示当前f(Ai),举例,A1匹配B4，有 A1匹配B1，有,看成一次事件,看成一次事件,分析,事件总数8n 根据Ai,Bi的有序性，预处理用指针即可,知道下一时刻k+1会发生的事件,更新sum,得到f (Ai)4种情况对应的Bj范围,每件事件发生时间,小结,算法流程如下 1将Ai,Bi排序 2预处理求出每个事件发生时间 3枚举和A1匹配的点Bk,更新sum。 4输出 时间复杂度 O(排序+事件总数)=O(nlgn),小结,将变化的Ci转化成“不变”的f(Ai)和g(Bi) 减少了操作规模 问题迎刃而解,总结,例一蚂蚁 以不变应万变 例二circular way 将变量的操作规模缩小,仔细分析，大胆猜想,把握问题的本质,问题迎刃而解,变 不变,谢谢大家,参考文献: 1 刘汝佳,黄亮.算法艺术与信息学竞赛. 清华大学出版社.2003 2 zju online judge 2376 ants. http:/acm.zju.edu.cn/show_problem.php?pid=2376 3 sgu online judge 313 circular railway. http:/acm.sgu.ru/problem.php?contest=0&problem=313,