| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 881 人关注过本帖
标题:墓地雕塑 思路讲解
只看楼主 加入收藏
longxingxiu
Rank: 2
等 级:论坛游民
帖 子:73
专家分:64
注 册:2014-4-23
结帖率:91.67%
收藏
已结贴  问题点数:2 回复次数:8 
墓地雕塑 思路讲解
题目描述:

在一个周长为10000的圆上等距分布着n个雕塑。现在又有m个新雕塑加入(位置可以随意放),希望所有n+m个雕塑在圆周上均匀分布。这就需要移动其中一些原有的雕塑。要求n个雕塑移动的总距离尽量小。
输入格式:

输入包含若干组数据。每组数据仅一行,包含两个整数n和m(2<=n<=1000, 1<=m<=1000),即原始的雕塑数量和新加的雕塑数量。输入结束标志为文件结束符(EOF)。
输出格式:
输入仅一行,为最小总距离,精确到0.0001。
样例输入:
2 1
2 3
3 1
10 10
1666.6667
1000.0
1666.6667
0.0
         我的想法是分别求出加之前和加之后的雕塑的坐标,求出离新坐标最近的旧坐标,并求出其差值,累计即为移动的最小距离。
下面是我的代码,不知道有没有其他的方法。
程序代码:
#include "stdio.h"
#include "math.h"
#define N 100
double a[N];
int main(void)
{
    int n,m;
    double*p=a;
    double dminsum=0.0;
    scanf("%d%d",&n,&m);
    int i,j;         
    //***以其中一个点为原点,不用动,剩下的点的坐标可以求出*******///
    //***思路是求出所有距离新坐标最近的旧坐标以及差值,累加********///
        for(i=1;i<n;i++)//n-1个点分别求新坐标到附近旧坐标的最小距离
     {
        for(j=1;j<m+n;j++)//将m+n-1个点的坐标求出,并求出一个原来点与后来所有点的距离存到*p中
        {
            *(p+j)=fabs((double)(10000*j/(m+n))-(double)(10000*i/n));//*(p+1)是第一个距离差值
        }
        for(j=1;j<m+n-1;j++)//求出差值中最小的作为一个旧坐标的移动距离,共m+n-2次比较,求最小值的方法
        {  
            if(*(p+1)>*(p+1+j))
                *(p+1)=*(p+1+j);
        }
        dminsum+=*(p+1);        
     }
    printf("%.41f\n",dminsum);
}
搜索更多相关主题的帖子: 墓地 
2014-05-07 16:35
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
怎么证明原点不动最优。


[fly]存在即是合理[/fly]
2014-05-07 17:16
longxingxiu
Rank: 2
等 级:论坛游民
帖 子:73
专家分:64
注 册:2014-4-23
收藏
得分:0 
回复 2 楼 azzbcc
总有一个点是不用动的嘛,这个不可以理解嘛?
2014-05-07 18:17
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
以下是引用longxingxiu在2014-5-7 18:17:20的发言:

总有一个点是不用动的嘛,这个不可以理解嘛?


不一定哦,谁说不能都动的


[fly]存在即是合理[/fly]
2014-05-07 18:46
砖家的谎言
Rank: 12Rank: 12Rank: 12
等 级:禁止访问
威 望:30
帖 子:693
专家分:3898
注 册:2013-12-6
收藏
得分:2 
可以有一部分不动的

我不是砖家,要努力成为砖家。
2014-05-07 19:14
longxingxiu
Rank: 2
等 级:论坛游民
帖 子:73
专家分:64
注 册:2014-4-23
收藏
得分:0 
回复 4 楼 azzbcc
没说不可以都懂,选择一个点相对不动的啊!
2014-05-07 20:28
longxingxiu
Rank: 2
等 级:论坛游民
帖 子:73
专家分:64
注 册:2014-4-23
收藏
得分:0 
回复 5 楼 砖家的谎言
嗯,是啊
2014-05-07 20:29
听说你爱笑
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2017-7-20
收藏
得分:0 
楼主,我也有个问题,有没有两个雕塑会移到相同的位置,怎么证明或者怎么理解,这个问题
2017-07-20 16:40
听说你爱笑
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2017-7-20
收藏
得分:0 
楼主,我也有个问题,有没有两个雕塑会移到相同的位置,怎么证明或者怎么理解,这个问题
2017-07-20 16:40
快速回复:墓地雕塑 思路讲解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.046072 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved