POJ3154 Graveyard

　　模型转换一下，把圆形的路从某个雕塑处剪开拉成一条直线，这样就很容易处理出添加雕塑前后的位置数组a[N]和c[N+M]。对于原状态的一个雕塑a[i]，在新位置数组c[N+M]中找出小于等于a[i]的位置c[j]，然后取位置j和其相邻两点j-1、j+1(如果有的话)距离的最小值(a[i] - min(c[j-1], c[j], c[j+1]))为a[i]须移动的最短距离。

　　原来想的时候会顾虑这样一个问题：在原来的位置数组a[N]中会不会出现相邻的两个点a[i],a[i+1]同时和c[j]距离最近，也就是说上述思想会不会导致a[i]和a[i+1]移到同一个位置？其实是不会出现这种情况的，可以画个数轴分析一下，如果雕塑增多了，那么原来雕塑肯定在新位置数组的两点之间，如果同时位于中点，上述分析显然成立，如果不同时位于中点，那么，便会偏向同一侧而不会取这两点中间的c[j]。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #define N 1005
 6 using namespace std;
 7 
 8 int n, m;
 9 double a[N], c[N * 2];
10 
11 int main()
12 {
13     int i;
14     double j, d, ans;
15     while(scanf("%d%d", &n, &m) == 2)
16     {
17         d = 10000.0 / n;
18         for(j = 0.0, i = 0; i < n; i ++, j += d)
19             a[i] = j;
20         d = 10000.0 / (n + m);
21         for(j = 0.0, i = 0; i < n + m; i ++, j += d)
22             c[i] = j;
23 
24         double k;
25         for(ans = 0.0, i = 0; i < n; i ++)
26         {
27             int loc = lower_bound(c, c + n + m, a[i]) - c;
28             k = fabs(a[i] - c[loc]);
29             if(loc > 0)
30                 k = min(k, fabs(a[i] - c[loc - 1]));
31             if(loc < n + m - 1)
32                 k = min(k, fabs(a[i] - c[loc + 1]));
33             ans += k;
34         }
35         printf("%.4f\n", ans);
36     }
37     return 0;
38 }