CF709B 题解

So_noSlack 的博客 / 2023-07-28 / 原文

洛谷链接&CF 链接

本篇题解为此题较简单做法及较少码量，并且码风优良，请放心阅读。

题目简述

给定 \(N\) 个点，在一条数轴上，位置为 \(x_1,…,x_n\)，你的位置为 \(p\)，你要经过 \(N-1\) 个点，求至少要走的距离。

思路

首先因为输入是乱序的，所以需要由小到大排序。

又因为需要经过 \(N-1\) 个点，所以要么不走左端点，要么不走右端点，这样分两种情况讨论，分别求出答案取 \(\min\) 即可。

首先分析情况 \(1\)，要么 \(p \le a_2 \le a_n\)，要么 \(a_2 \le p \le a_n\)，要么 \(a_2 \le a_n \le p\)，第二种不论先去 \(a_2\) 还是 \(a_n\) 结果都一样。所以不讨论，第一三种需要讨论一下，对于第一种一定是先去 \(a_2\) 结果最小，对于第三种一定是先去 \(a_n\) 结果最小，只需对这两种分别处理最后取 \(\min\) 即可，由此分析可得这种情况的方程式为：

\[\min( | a_n - p | + | a_n - a_2 |, | a_2 - p | + | a_n - a_2 | ) \]

同样分析可得情况 \(2\) 的方程式：

\[\min( | a_{n - 1} - p | + | a_{n - 1} - a_1 |, | a_1 - p | + | a_{n - 1} - a_1 | ) \]

最后对两种情况取 \(\min\) 即可。

经过以上分析，很容易即可得出代码了：

#include<iostream>
#include<algorithm>
using namespace std;

int n, a[100005], p;
long long ans = 0x3f3f3f3f; // 要取 min 所以需初始化一个较大数

int min(int x, int y) { return (x < y) ? x : y; }

int abs(int x) { return (x > 0) ? x : -x; }

int main(){
	cin >> n >> p;
	if(n == 1) { cout << "0\n"; return 0; } // 特判
	for(int i = 1; i <= n; i ++) cin >> a[i];
	sort(a + 1, a + n + 1); // 因为是乱序，所以需要排序
	long long num1 = 0, num2 = 0; // 可不开 long long
	// 情况 1
  	num1 = min(abs(a[n] - p) + abs(a[n] - a[2]), abs(a[2] - p) + abs(a[n] - a[2]));
  	// 情况 2
	num2 = min(abs(a[n - 1] - p) + abs(a[n - 1] - a[1]), abs(a[1] - p) + abs(a[n - 1] - a[1]));
	ans = min(num1, num2); // 答案取 min
	cout << ans << endl; // 输出，换行好习惯
	return 0;
}

提交记录：

SonoSlack