Gym 101246J Buoys（三分查找）

http://codeforces.com/gym/101246/problem/J

题意：

给定x轴上的n个点的坐标，按顺序从左到右给出，现在要使得每个点的间距相同，可以移动每个点的坐标，但是不能改变点的相对顺序。求总共最少需要移动多少距离和移动后点的坐标。

思路：

一开始想到用二分搜索，然后枚举一个点为不动点，但是这样我不知道该怎么去改变L、R的值了。。

仔细想想，这道题目所对应的模型图应该是这样的：

中间存在一点可以使移动距离最短，两边很大，因为间距设置的太小和太大都需要移动很多距离。这道题目可以用三分查找做。

三分查找是这样的：

MID=（L+R）/2， MMID=（MID+R）/2

接下去去计算MID和MMID这两个点所对应值，如果cla(MID)>cla(MMID)，那么L=mid，否则的话，R=MMID。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 using namespace std;
12 typedef long long ll;
13 typedef pair<int,int> pll;
14 const int INF = 0x3f3f3f3f;
15 const int maxn=400+5;
16 const double eps=1e-10;
17 
18 int n;
19 int x[maxn];
20 
21 double MIN;
22 double ans[maxn];
23 double p[maxn];
24 
25 double solve(double dis)
26 {
27     double tmmp=INF;
28     for(int i=1;i<=n;i++)
29     {
30         double tmp = 0;
31         p[i]=x[i];
32         for(int j=i-1;j>0;j--)
33         {
34             tmp+=abs(p[j+1]-x[j]-dis);
35             p[j]=p[j+1]-dis;
36         }
37         for(int j=i+1;j<=n;j++)
38         {
39             tmp+=abs(x[j]-p[j-1]-dis);
40             p[j]=p[j-1]+dis;
41         }
42 
43         if(tmp<MIN)
44         {
45             MIN=tmp;
46             memcpy(ans,p,sizeof(p));
47         }
48         if(tmp<tmmp)
49             tmmp = tmp;
50     }
51     return tmmp;
52 }
53 
54 int main()
55 {
56     freopen("input.txt","r",stdin);
57     freopen("output.txt","w",stdout);
58     //freopen("in.txt","r",stdin);
59     while(~scanf("%d",&n))
60     {
61         for(int i=1;i<=n;i++)
62             scanf("%d",&x[i]);
63 
64         double L = 0, R=0;
65         for(int i=1;i<n;i++)
66             R=max(R,(double)(x[i+1]-x[i]));
67 
68         MIN = INF;
69 
70         while(R-L>=eps)
71         {
72             double mid = (L+R)/2.;
73             double mmid = (mid+R)/2.;
74             if(solve(mid)>solve(mmid))  L=mid;
75             else R=mmid;
76         }
77 
78         printf("%.4f
",MIN);
79         for(int i=1;i<=n;i++)
80         {
81             printf("%.7f%c",ans[i],i==n?'
':' ');
82         }
83     }
84     return 0;
85 }