这题大意是说有一个Image,里面可以有2个-10亿个象素点,要求计算每个点与它相邻八个点的差的绝对值的最大值,然后用压缩格式输出. 内存限制10M,运行时间1s

   数据量大,不能全部load入内存.我用2个索引数组记录每个象素的起始位置和长度,用Binary search可以搜索第i个象素相邻八个点的值.
   如果有多行以上的象素值相同就可以变成0输出去.
   但问题是Image很宽的时候这种方法就会Time limited..
上面的方法不太好,于是考虑动态规划.
一些细节问题:
对第k个segment(设为Sk)的更新的边界点应该包括:包围S(k)的其他S(k-r),S(k-r-1)..S(k-1),S(k+1)..S(k+p)的头点和结点.这个方向是"从外到里"更新的Sk的.
还有一种"从里到外"更新Sk,就是Sk的头点和尾点分别与它们周围八个点比较的更新.
两种更新做完后得到一个序列
(a1,a2,aj,-1.....-1,ak..,alen) 其中 aj和ak不为-1,它们中间的部分全部为-1(表示它们没更新过), 也有可能是-1出现在边路.
如果aj和ak不在用一行, 全部输出0
否则,就全部改为aj或者ak输出.类似后面也可能有连续的-1,也是这样处理.

如果输入只有一行一列或者只有一组pixel的情况,特殊处理.

• Re:偶是这么想的,各位大牛有何高见? (682) gzw_02 2008-05-20 14:58:17