首页 > 代码库 > 双调欧几里得旅行商问题
双调欧几里得旅行商问题
杭电ACM的一道题~~
Problem Description
有很多从磁盘读取数据的需求,包括顺序读取、随机读取。为了提高效率,需要人为安排磁盘读取。然而,在现实中,这种做法很复杂。我们考虑一个相对简单的场景。
磁盘有许多轨道,每个轨道有许多扇区,用于存储数据。当我们想在特定扇区来读取数据时,磁头需要跳转到特定的轨道、具体扇区进行读取操作。为了简单,我们假设磁头可以在某个轨道顺时针或逆时针匀速旋转,旋转一周的时间是360个单位时间。磁头也可以随意移动到某个轨道进行读取,每跳转到一个相邻轨道的时间为400个单位时间,跳转前后磁头所在扇区位置不变。一次读取数据的时间为10个单位时间,读取前后磁头所在的扇区位置不变。磁头同时只能做一件事:跳转轨道,旋转或读取。
现在,需要在磁盘读取一组数据,假设每个轨道至多有一个读取请求,这个读取的扇区是轨道上分布在 0到359内的一个整数点扇区,即轨道的某个360等分点。磁头的起始点在0轨道0扇区,此时没有数据读取。在完成所有读取后,磁头需要回到0轨道0扇区的始点位置。请问完成给定的读取所需的最小时间。
磁盘有许多轨道,每个轨道有许多扇区,用于存储数据。当我们想在特定扇区来读取数据时,磁头需要跳转到特定的轨道、具体扇区进行读取操作。为了简单,我们假设磁头可以在某个轨道顺时针或逆时针匀速旋转,旋转一周的时间是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),表示每个数据的磁道和扇区,磁道是按升序排列,并且没有重复。
对于每组测试数据,第一行包含一个整数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
这样写提交后提示memory过大,到33M了,所以还是想办法优化这个b[1001][1001]的数组,这个数组就很大,到80M左右。
1 //双调欧几里得旅行商问题 2 3 //PKU 2677 4 #include<stdio.h> 5 #include<math.h> 6 #include<stdlib.h> 7 #define R 1001 8 int dis(int i,int j); 9 void shortway( int **b,int N); 10 struct Node 11 { 12 int x; 13 int y; 14 }a[1001]; 15 int main(void) 16 { 17 int M,N,i,j,k; 18 int **b; 19 int s[R]={0}; 20 a[0].x=0;a[0].y=0; 21 scanf("%d",&M); 22 for(i=0;i<M;i++) 23 { 24 scanf("%d",&N); 25 //二级指针开辟一个二维数组 26 b=(int**)malloc((N+1)*sizeof(int));//b是指向指针的指针 27 for(j=0;j<N+1;j++) 28 b[j]=(int*)malloc((N+1)*sizeof(int));//b[j]是指针 29 // 30 for(j=0;j<N+1;j++) 31 for(k=0;k<N+1;k++) 32 b[j][k]=0; 33 34 for(j=1;j<=N;j++) 35 { 36 scanf("%d%d",&a[j].x,&a[j].y); 37 } 38 shortway(b,N); 39 s[i]=b[N][N]+N*10; 40 free(b); 41 } 42 for(i=0;i<M;i++) 43 printf("%d\n",s[i]); 44 45 return 0; 46 } 47 int dis(int i,int j) 48 { 49 int m,m1,m2; 50 m1=abs(a[i].x-a[j].x)*400; 51 m2=abs(a[i].y-a[j].y); 52 m2=m2>(360-m2)?(360-m2):m2; 53 return m=m1+m2; 54 } 55 void shortway(int **b,int N) 56 { 57 int i,j,k; 58 int num; 59 b[0][0]=0; 60 for(i=1;i<=N;i++) 61 for(j=0;j<=i;j++) 62 { 63 if(i==j) 64 b[i][j]=b[i][j-1]+dis(i,j-1); 65 if(i>j+1) 66 b[i][j]=b[i-1][j]+dis(i-1,i); 67 if(i==j+1) 68 { 69 70 b[i][j]=(int)pow(2,30);//?? 71 if(j==0) 72 b[i][j]=b[0][0]+dis(1,0); 73 for(k=0;k<j;k++) 74 { 75 num=b[k][j]+dis(k,i); 76 //printf("%d,%d,%d\n",b[k][j],dis(k,i),num); 77 if(b[i][j]>num) 78 b[i][j]=num; 79 } 80 } 81 b[j][i]=b[i][j]; 82 } 83 }
可是不用malloc动态分配内存,int b[R][R],4*8*10^6大概32M,根本编译不了,对于双调问题我找到的算法也只有这种,怎么优化这里的内存?还是考虑优化算法吧
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。