SPOJ 1644 - Trees[TREEOI14]

张文泰 posted @ 2010年3月26日 16:00 in Art of Science with tags SPOJ 数据结构 , 4248 阅读

题目的意思很明确,就是要求出一组绝对值函数的最小值。由于规模较大,我们要找出一个n2以下复杂度的算法。

对于一般的绝对值求最值问题,我们首先想到的是把绝对值的符号打开,然后再加以讨论。这个题目也不外如是。打开绝对值符号之后,我们发现,如果在i和j中能够确定一个值,那么就变成了一个查找最优值的问题。

我们如果能够确定i,那么加上确定了|xj-xi-1|+|xj-xi+1|两者的符号,我们就可以确定xj的范围。这时候,我们还是没有办法直接找到最小值的。这是因为|xi-xj-1|+|xi-xj+1|的存在,使得xj-1和xj+1的取值也受到了限制。我们可以想办法把这个限制给去掉。

显然我们需要合理地安排查询顺序。由于绝对值符号展开后,我们可以得到最值的表达式,对于不同的i,我们都能构造出关于j的函数使得这些函数都能够适用。也就是说,产生一个关于j的函数,使得查找变成求这个函数的最值,就可以求出问题的最值。

我们要想办法把这个关于j的函数的最值转化为在某个范围内求最值的问题。通常想到的就是区间查询问题。这里我们需要避免高维的区间查找情形。

我们考察所有式子展开的情况。如果|xi-xj-1|+|xi-xj+1|的符号都是正,那么xi的范围就是大于xj-1和xj+1的较大值,这样,我们把xj按照xj-1和xj+1的较大值从小到大排序,同时如果查找也是按照xi从小到大的顺序进行,那么就可以用两个指针维护查找过程,达到O(n)的外循环复杂度,而且不会与条件冲突,同时建立一维线段树,按照|xj-xi-1|+|xj-xi+1|的符号进行相关区间的最值查找。

如果|xi-xj-1|+|xi-xj+1|的符号都是负,也是差不多的情形。需要商榷的就是xi在xj-1与xj+1之间的情况。这时,我们可以把它们看成一个区间[xj-1, xj+1],把这些区间按照一定顺序排序,再通过这些区间来确定i的范围,再来完成查找就可以了。这里需要判断某个i会在哪些区间中,这样,查找一个i的复杂度就是O(log2 n)。这里需要借鉴这里的数据结构:2D de aici

由于只有最后一种情况的单次查找复杂度是O(log2 n),我们得到的算法复杂度是O(nlog2 n)。绝对值打开之后一共有8种情况,我们需要逐一讨论,相当繁琐。


本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter