CF30D

清小秋ovo · 2022-01-06 18:45:37 · 题解

CF30D

计算几何 + 贪心

题意

有 n + 1 个点，其中 n 个点都在数轴 x 轴上。 求最短的从第 k 个点开始的走过所有点的最短距离，允许重复。 n ≤ 10^5

题解

首先考虑起始点是第 n+1 个点。

答案无非两种:

再考虑当起点处在数轴上时的情况:

一定存在 x 轴上某点 k，使得人先走遍 1\sim k，回来，再走遍 k + 1\sim n；

或者先走遍 k +1\sim n，回来，再走遍 1\sim k. 于是我们考虑 2 个情况：

从点 p 出发，走一个区间 [l ,r]。

最佳方案显然是从 p 到 l 或 r 中较近的一个，然后一路走到 对面。 距离是 dist (a_l ,a_r ) + \min(dist(p,a_l ),dist(p,a_r ))。

从点 k 出发，走一个区间 [l ,r]，再回到 p。 最佳方案可以证明是从 k 走到l或 r 中的某一个， 然后走到对面，然后走到 p。 距离是 |a_l-a_r| + \min(|a_k-a_l| +dist(r),| a_k-a_r | +dist(l))。

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

int k,i,j,n;
double ans,x[100010],xp,yp,xk;

double C(int z){  return hypot(x[z]-xp,yp); }  

double A(int l,int r){  return x[r]-x[l]+min(C(l),C(r)); } //l->r->p 

double B(int l,int r){  return x[r]-x[l]+min(abs(xk-x[l])+C(r),abs(xk-x[r])+C(l)); }//k->l->r->p

void inlinework(){  //给定起点在轴上
  ans=B(1,n);  //起点为断点的情况
  for (i=2;i<=n;i++){ //从2开始 
    double t=min(A(1,i-1)+B(i,n),A(i,n)+B(1,i-1));
    if (t<ans) ans=t;
  }
}

void outlinework(){  //给定起点就是轴外点时必为最优
    ans=A(1,n);
}

int main()
{
    freopen("kings.in","r",stdin);
    freopen("kings.out","w",stdout);
    scanf("%d%d",&n,&k);
    for (i=1;i<=n;i++) scanf("%lf",&x[i]); 
    scanf("%lf%lf",&xp,&yp);
    xk=x[k];
    sort(x+1,x+n+1);
    if (k<=n) inlinework();
    else outlinework();
    printf("%.20lf\n",ans);
}