南昌网站建设公司/旅游app推广营销策略

题意：

          给出 N 个跳点和 M 个目标点，跳点之间可任意传送，问从第一跳点开始，走遍所有目标点并返回第一跳点的最小 cost 是多少？

思路：

          见代码

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,inf=0x7fffffff;
long long t[N],b[N],c[N],d[N];
int n,m;
int main()
{scanf("%d %d",&n,&m);t[0]=-inf,t[n+1]=inf;for(int i=1;i<=n;i++) scanf("%lld",&t[i]);for(int i=1;i<=m;i++) scanf("%lld",&b[i]);b[0]=b[m+1]=t[1];for(int i=1,j=0;i<=m;i++){while(t[j+1]<=b[i]) j++;if(j>0) c[i]=b[i]-t[j];else c[i]=inf;if(j<n) d[i]=t[j+1]-b[i];else d[i]=inf;c[i]=min(c[i],d[i]);}long long ans=0;//....................................................c 最近跳点的costc[0]=c[m+1]=0;for(int i=1;i<=m+1;i++){//............................m+1 最后一点返回long long temp=abs(b[i-1]-b[i]);//................temp 最近两点的costtemp=min(temp,c[i-1]+c[i]);//.....................上一点的返回cost+这一点的cost 或 点对点的 costans+=temp;}printf("%lld\n",ans);
}