并行

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 parellel.in 输出文件 parellel.out

【问题描述

    为了改善计算机的I/O性能,并行技术被广泛应用。许多计算机都有一个磁带机,容量为32767,适合于16位地址系统(其中最高位用来表示读写状态),传统的结构只有一个读写臂,读写臂带动磁头在磁带的表面上移动,就像留声机的唱针在唱片上滑动一样,操作系统使用指令控制读写臂将磁头移至磁带上指定的位置。
   但是在我们的并行磁带机中,磁带被拉长成带状,从一面到另一面上面记录的信息都按顺序被编号,最有特色的是,它有N个读写臂,并能保证在磁带上操作时不发生冲突,因此系统可以一次存取N个记录,如下图所示:


   有时我们可能不需要读/写N个不同的记录,比如,可能我们只需N-1个,但是经过了之前的一些操作,N个读写臂都停在了某个地方,这时它们必须准确找到我们需要的信息所存放的地点,读写臂从记录A移动到记录B的距离为|A-B|,出于某种灵活的因素,一条指令所要读取的N-1个记录不一定是互不相同的,这样便会有一些读写头停在相同的位置,但是读写臂不会停在指令中没有要求读/写的记录上。
   你的任务是确定移动N个读写臂去读/写N-1个记录,所有的读写头所移动的距离和的最小值。
 
【输入格式】
   输入文件包含多组测试数据,文件的结束为单独的一行只含一个数字0。
   每一组测试数据的格式如下:
   N
   P1 P2 ... PN
   r1 r2 ... rN-1
   其中所有的数据项都是整数,N表示读写臂的个数(2≤N≤10000),第二行的N个整数P1,...,PN表示读写臂的位置,整数r1,...,rN表示我们想要在磁带上读/写的位置,所有这些整数均是非负的并且不超过32767。
【输出格式】

    对于每一组测试数据,在单独一行输出你找到的最小距离。

【输入样例】
输入文件名:parellel.in
3
1 3 6
2 5
0
输出文件名:parellel.out
3