首页 > ACM题库 > UVA > Uva-1388-Graveyard[数学]
2014
02-25

Uva-1388-Graveyard[数学]

Graveyard

Programming contests became so popular in the year 2397 that the governor of New Earck — the largest human-inhabited planet of the galaxy — opened a special Alley of Contestant Memories (ACM) at the local graveyard. The ACM encircles a green park, and holds the holographic statues of famous contestants placed equidistantly along the park perimeter. The alley has to be renewed from time to time when a new group of memorials arrives.

When new memorials are added, the exact place for each can be selected arbitrarily along the ACM, but the equidistant disposition must be maintained by moving some of the old statues along the alley.

Surprisingly, humans are still quite superstitious in 24th century: the graveyard keepers believe the holograms are holding dead people souls, and thus always try to renew the ACM with minimal possible movements of existing statues (besides, the holographic equipment is very heavy). Statues are moved along the park perimeter. Your work is to find a renewal plan which minimizes the sum of travel distances of all statues. Installation of a new hologram adds no distance penalty, so choose the places for newcomers wisely!

Input 

The input file contains several test cases, each of them consists of a a line that contains two integer numbers: n – the number of holographic statues initially located at the ACM, and m – the number of statues to be added (2$ \le$n$ \le$1000, 1$ \le$m$ \le$1000) . The length of the alley along the park perimeter is exactly 10 000 feet.

Output 

For each test case, write to the output a line with a single real number — the minimal sum of travel distances of all statues (in feet). The answer must be precise to at least 4 digits after decimal point.

\epsfbox{p3708.eps}

Pictures show the first three examples. Marked circles denote original statues, empty circles denote new equidistant places, arrows denote movement plans for existing statues.

Sample Input 

2 1 
2 3 
3 1 
10 10

Sample Output 

1666.6667 
1000.0 
1666.6667 
0.0

思想和UVA-11300-Spreading the Wealth[中位数] 此题有些类似。找一个定点作为原点,此点是不需要移动的。但是代码需要这技巧。书中是把园等比例缩小为周长为n,同时floor(x+0.5)先进行四舍五入,然后然后向下取整,求得新的坐标,最后再将结果*10000还原。

书上的代码:

#include <cstdio>
#include <cmath>
int main ()
{
 //   freopen("in.txt","r",stdin);
    int n, m;
    double pos, ans;
    while(scanf("%d%d",&n,&m)==2)
    {
        ans = 0.0;
        if(m!=n) for(int i = 1; i < n; i++)
        {
            pos = 1.0*i/n*(m+n);//求得需要移动的坐标,其中*(m+n)是为了与下面求和通分,很巧妙
            ans += fabs(pos-floor(pos+0.5))/(n+m);
        }
        printf("%.4lf\n",ans*10000);
    }
    return 0;
}

ACM之家原创,链接:http://www.acmerblog.com/uva-1388-graveyard-4603.html


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。