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 }
转载于:https://www.cnblogs.com/Tree-dream/p/7347954.html
