首页 > 代码库 > uva 3708

uva 3708

2024-11-25 03:10:40   204人阅读

https://vjudge.net/problem/15133/origin

题意：有一个环，原来有m个点，间隔相同的依次隔开，后来插入n个点，求最少移动的距离

思路：这个题和uva 10881有点类似，我的想法是说，既然是找最近的，那么肯定是最多n-1个点来移动

那么怎么看他移动的距离呢，我们可以用一个数组，这个数组来记录一下这原来n个点所在的位置，然后后来n+m个点所在的位置

然后找出原来的n个点，在它隔壁的两个点，找距离近的那个点，就肯定是它所移动所需最短的距离了

题目还是独立思考，即使每天做的量少，但是只要是在你知识体系内的，你应该可以解决--来自一位大神说的话

 

 

 1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 #define eps 1e-4 8 int m,n; 9 10 struct Node{11     double x;12     int flag;13 }tmp[3005];14 15 int cmp(const Node &a,const Node &b)16 {17     return a.x-b.x<eps;18 }19 20 int main()21 {22     double first ,second;23     while(~scanf("%d%d",&m,&n))24     {25         first = 1.0*10000/m;26         second = 1.0*10000/(m+n);27         if(!(n%m))28             printf("0.0\n");29         else{30             for(int i = 0;i<m;i++)31             {32                 tmp[i].x = i*first;33                 tmp[i].flag = 1;34             }35             for(int i = m;i<m+n+m;i++)36             {37                 tmp[i].x = (i-m+1)*second;38                 tmp[i].flag = 0;39             }40             sort(tmp,tmp+m+n+m,cmp);41             double ans = 0;42             for(int i = 1;i<m+n+m;i++)43             {44                 if(tmp[i].flag==1)45                 {46                     ans+=min(fabs(tmp[i].x-tmp[i-1].x),fabs(tmp[i].x-tmp[i+1].x));47                 }48             }49             printf("%.4lf\n",ans);50         }51     }52     return 0;53 }

 

uva 3708


联系
我们