首页 > 代码库 > HDU4824 双调欧几里得

HDU4824 双调欧几里得

2024-07-09 04:18:11   212人阅读

Disk ScheduleTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 240    Accepted Submission(s): 121Problem 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 Input311 1031 203 305 1021 102 11 Sample Output83040901642

 

第一次学双调欧几里得。。

双调欧几里得详解网上都有，在这就不贴出来了，只谈谈我对双调欧几里得的理解。

对于一个平面里的n个点，找出一条回路经过每个点一次，且路径最短。

把n个点分别标为1-n，dis(i,j)即为点i与点j直接相连的路径长度，dp[i][j]（i>j）为连接前i个点的一条路径，且不是封闭的，i与j之间没有连线，就相当于一条线以i为首，以j为尾把前i个点串起来。

那么有dp[i][i-1]=min(dp[i-1][k]+dis(k,i))    //k<i-1，若想在前i-1个点相连的线上再串上点i且以i-1这个点为尾，那么就找出所有前i-1个点相连的线且以i-1为首k为尾+点k与                                                                   点i之间距离    最小的线即为dp[i][i-1]

dp[i][k]=dp[i-1][k]+dis(i,i-1)   //k<i-1，若想把i串到线上，且这条线以i和k为两段，那么找出以i-1和k为两端的线，把i串到i-1那一头即可。

上述过程中的路径都是断开的即不是环。

那么如何求环呢，把n个点相连的线两头接起来就行了，即dp[n][k]+dis(n,k)。

 

对于本题，跳转轨道时只能挨个跳轨道，那么跳轨道的时间即为从0轨道一格一格跳到最大轨道处，然后再一格一格跳回来，这个好算。

然后是读取数据时间即为数据个数*10。

难点就是跳0-359范围的扇区时间，由于上述知识易知，最短的时间也就是把分布在0-359范围扇区只走一遍且是回路。

运用上述知识就可以写代码了，代码就不解释了：

 

 

 1 #include <stdio.h> 2 #include <string.h> 3 #include <string> 4 #include <algorithm> 5 #define inf 999999999 6 using namespace std; 7  8 long long int dp[1005][1005]; 9 int n;10 int a[1005];11 12 int dis(int i,int j)13 {14     int x1=a[i], x2=a[j];15     if(x1<x2)16     swap(x1,x2);17     return min(x1-x2,360-(x1-x2));18 }19 20 long long int DP()21 {22     int i, j;23     long long ans=0;24     dp[0][1]=dp[1][0]=dis(0,1);25     for(i=2;i<=n;i++)26     {27         dp[i][i-1]=inf;28         for(j=0;j<i-1;j++)29         {30             dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis(i,j));31             dp[i][j]=dp[i-1][j]+dis(i,i-1);32         }33     }34     ans=inf;35     for(i=0;i<n;i++)36     ans=min(ans,dp[n][i]+dis(n,i));37     return ans;38 }39 40 main()41 {42     int t, i, j;43     int m;44     scanf("%d",&t);45     while(t--)46     {47         scanf("%d",&n);48         for(i=1;i<=n;i++)49         scanf("%d %d",&m,&a[i]);50         printf("%I64d\n",DP()+n*10+m*800);51     }52 }

 

 

 


联系
我们