首页 > 代码库 > 双调欧几里得旅行商问题

双调欧几里得旅行商问题

2024-07-04 23:14:50   226人阅读

杭电ACM的一道题~~
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

这样写提交后提示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,根本编译不了，对于双调问题我找到的算法也只有这种，怎么优化这里的内存？还是考虑优化算法吧

 


联系
我们