Codeforces Gym101246J：Buoys（三分搜索）

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

题意：给出n个点坐标，要使这些点间距相同的话，就要移动这些点，问最少的需要的移动距离是多少，并输出移动后的坐标。

思路：昨晚比赛确定的一点就是通过X分搜索去枚举间距，使得最后的移动距离最短。

不过使用的是二分，而且写的时候也只枚举了起点和终点，后面想了要枚举所有的点，但时间来不及。

因为间距的单调不会使得答案单调，间距过大过小都会使得最后的移动距离不是最优，所以是使用三分而不是二分，顺便重温一下三分。

     while(fabs(r - l) > eps) {

         double mid = (l + r) / 2.0;

         double midd = (mid + r) / 2.0;

         if(cal(mid, ) > cal(midd, )) l = mid;

         else r = midd;

     }

     double ans = cal(l, ) > cal(r, ) ? r : l;

对于每次三分，每次在n个点里面假设一个点不动，然后枚举完算一遍，取最优。

而且据说挺卡精度的，直接开了1e-12.

 #include <bits/stdc++.h>

 using namespace std;

 #define N 405

 const double eps = 1e-;

 double num[N];

 int n, id;

 double cal(double x, int flag) {

     double res = , ans = ;

     for(int st = ; st <= n; st++) {

         res = ;

         for(int i = ; i < st; i++)

             res += fabs(num[st] - (st - i) * x - num[i]);

         for(int i = st + ; i <= n; i++)

             res += fabs(num[st] + (i - st) * x - num[i]);

         if(ans > res) ans = res, id = st;

     }

     return ans;

 }

 void solve() {

     scanf("%d", &n);

     for(int i = ; i <= n; i++) scanf("%lf", &num[i]);

     double l = , r = ;

     while(fabs(r - l) > eps) {

         double mid = (l + r) / 2.0;

         double midd = (mid + r) / 2.0;

         if(cal(mid, ) > cal(midd, )) l = mid;

         else r = midd;

     }

     double ans = cal(l, ) > cal(r, ) ? r : l;

     double res = cal(ans, );

     printf("%.4f\n", res);

     for(int i = ; i < id; i++)

         printf("%.10f ", num[id] - (id - i) * ans);

     printf("%.10f ", num[id]);

     for(int i = id + ; i <= n; i++)

         printf("%.10f ", num[id] + (i - id) * ans);

 }

 int main() {

     freopen("input.txt", "r", stdin);

     freopen("output.txt", "w", stdout);

     solve();

     return ;

 }

巴特西

Codeforces Gym101246J：Buoys（三分搜索）

最新文章

热门文章