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