旅行家问题1

NC221828. 旅行家问题1

描述

lzh最近在学习旅行家问题，为了照顾太菜的他，学长给他出了一个一维的问题，好让他对生活抱有希望。在一个数轴上面，散落着 $n$ 个城市，每个城市的坐标由 $x_i$ 表示。
给定旅行家的坐标，他每走一个单位长度需要的时间为1s，求他访问所有城市需要的最小时间。

输入描述

第一行包含两个正整数  ， 表示需要访问的城市数量以及lzh最初所在城市的坐标。
第二行包含  个正整数  ，表示要访问的城市的位置坐标。

输出描述

输出一个正整数，代表旅行家访问所有城市需要的最短时间。

示例1

输入:

2 3
2 4

输出:

说明:

从（3）走到（2）再走到（4），总时间为3s

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 43ms, 内存消耗: 776K, 提交时间: 2021-10-23 11:20:32

#include<bits/stdc++.h>
using namespace std;

int a[300000];

int main(){
  int n,x;
  cin >> n >> x;
  for(int i=1;i<=n;i++)cin >> a[i];
  sort(a+1,a+n+1);
  cout << a[n]-a[1]+min(abs(x-a[1]),abs(a[n]-x));
}

Python3 解法, 执行用时: 60ms, 内存消耗: 15704K, 提交时间: 2021-12-16 01:27:31

n,x=map(int,input().split())
a=list(map(int,input().split()))
l=min(a)
r=max(a)
if l<=x<=r: print(min(x-l,r-x)+r-l)
elif x>r: print(x-l)
elif x<l: print(r-x)