首页 > 代码库 > 2014 百度之星题解 1002 - Disk Schedule

2014 百度之星题解 1002 - Disk Schedule

Problem Description
有非常多从磁盘读取数据的需求,包含顺序读取、随机读取。为了提高效率,须要人为安排磁盘读取。然而,在现实中,这样的做法非常复杂。我们考虑一个相对简单的场景。 磁盘有很多轨道,每一个轨道有很多扇区,用于存储数据。当我们想在特定扇区来读取数据时,磁头须要跳转到特定的轨道、详细扇区进行读取操作。为了简单,我们如果磁头能够在某个轨道顺时针或逆时针匀速旋转,旋转一周的时间是360个单位时间。磁头也能够任意移动到某个轨道进行读取,每跳转到一个相邻轨道的时间为400个单位时间,跳转前后磁头所在扇区位置不变。一次读取数据的时间为10个单位时间,读取前后磁头所在的扇区位置不变。磁头同一时候仅仅能做一件事:跳转轨道,旋转或读取。 如今,须要在磁盘读取一组数据,如果每一个轨道至多有一个读取请求,这个读取的扇区是轨道上分布在 0到359内的一个整数点扇区,即轨道的某个360等分点。磁头的起始点在0轨道0扇区,此时没有数据读取。在完毕全部读取后,磁头须要回到0轨道0扇区的始点位置。请问完毕给定的读取所需的最小时间。
 

Input
输入的第一行包括一个整数M(0<M<=100),表示測试数据的组数。 对于每组測试数据,第一行包括一个整数N(0<N<=1000),表示要读取的数据的数量。之后每行包括两个整数T和S(0<T<=1000,0<= S<360),表示每一个数据的磁道和扇区,磁道是按升序排列,而且没有反复。
 

Output
对于每组測试数据,输出一个整数,表示完毕所有读取所需的时间。
 

Sample Input
3 1 1 10 3 1 20 3 30 5 10 2 1 10 2 11
 

Sample Output
830 4090 1642

本题是本次题目中最难的题目了,由于通过的人数最小,不断有人觉得自己的程序正确而无法通过。

大概非常多人都使用了简单的暴力法去解决这道题目,而这是个错误的方法,当然WA啦。

正确的解法应该是bitonic TSP - 能够參考<Introduction to Algorithm>第15章的练习题。

由于题目限定了每一个数据都须要訪问一次,并且是须要从出发点出发,最后回到出发点的,形成完美符合Bitonic TSP的问题。



如上图的b图就是Bitonic TSP的路线,a是最优路线,可是这里的问题限定了并不须要TSP的最优路线。

发散思考:

1 并非模拟读数据的方式从開始出发读数据,然后再往回读,而是想象有两个读数据的磁头,一直读到结尾点,两磁头重合。

2 读数据的时间另外计算:N * 10(N个数据,每一个数据须要10个单位时间。


#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <vector>
using namespace std;

class DiskSchedule_3
{
	struct TS
	{
		int T, S;
	};

	int getDist(vector<TS> &gra, int i, int k)
	{
		int d = (gra[k].T-gra[i].T) * 400;
		if (abs(gra[k].S-gra[i].S) <= 180) d += abs(gra[k].S-gra[i].S);
		else d += 360 - abs(gra[k].S-gra[i].S);
		return d;
	}
public:
	DiskSchedule_3()
	{
		int M, N;
		scanf("%d", &M);
		while (M--)
		{
			scanf("%d", &N);
			vector<TS> gra(N+1);
			for (int i = 1; i <= N; i++)
			{
				scanf("%d %d", &gra[i].T, &gra[i].S);
			}
			vector<vector<int> > tbl(N+1, vector<int>(N+1));
			for (int i = 1; i <= N; i++)
			{
				for (int k = 0; k <= i; k++)
				{
					if (k+1 < i) 
						tbl[k][i] = tbl[k][i-1] + getDist(gra, i-1, i);
					else
					{
						tbl[k][i] = tbl[0][k] + getDist(gra, 0, i);
						for (int r = 1; r < i; r++)
						{
							int d = tbl[r][k] + getDist(gra, r, i);
							tbl[k][i] = min(tbl[k][i], d);
						}
					}
				}
			}
			printf("%d\n", tbl[N][N] + 10 * N);
		}
	}
};