题目描述

难度分:$1500$

输入$n(1 \leq n \leq 10^5)$，$x(-10^6 \leq x \leq 10^6)$和长为$n$的数组$a(-10^6 \leq a[i] \leq 10^6)$。

一维数轴上有$n$个苹果，坐标记录在数组$a$中。你一开始在$x$处。你需要收集至少$n-1$个苹果。输出最少移动距离。

输入样例$1$

3 10
1 7 12

输出样例$1$

7

输入样例$2$

2 0
11 -10

输出样例$2$

10

输入样例$3$

5 0
0 0 1000 0 0

输出样例$3$

0

算法

有序表+贪心

构建一个有序表的映射$counter$，表示“坐标位置$\rightarrow$该位置上的苹果个数”。首先需要知道，如果要将$[l,r]$内的苹果全部收集到，最少需要走多少步？分为以下三种情况讨论：

1. $x \leq l$，从$x$走到$r$，最少步数为$r-x$。
2. $x \geq r$，从$x$走到$l$，最少步数为$x-l$。
3. $l \lt x \lt r$，从$x$走到某个端点，再走完$[l,r]$整段。可以发现后者是个定值，所以只要最小化前者即可，也就是离哪个端点近就往哪边先走，最少步数为$min(x-l,r-x)+r-l$。

因此，收集$n$个苹果的答案就是$[L,R]$上的最少步数，其中$L$是最左苹果的位置，$R$是最右苹果的位置。如果收集$n-1$个苹果，那么这个未被收集的苹果一定在端点上，那就需要满足这个端点上只有一个苹果，如果有多个苹果这种情况就肯定不存在了。

1. 如果左端点上只有一个苹果，那么答案就是$[L’,R]$上的最少步数。$L’$表示次左位置的苹果坐标。
2. 如果右端点上只有一个苹果，那么答案就是$[L,R’]$上的最少步数。$R’$表示次右位置的苹果坐标。

以上几种情况取最小值就是最终答案，但是需要注意$n=1$的情况，这时候是不存在次左和次右位置的，需要特判。

复杂度分析

时间复杂度

预处理出映射表$counter$的时间复杂度是$O(nlog_2n)$的，后面分情况讨论求答案是$O(1)$的，所以整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间消耗的瓶颈就在于$counter$表，在最差情况下需要存$O(n)$级别的键值对。所以整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
int n, x;

int get(int low, int high) {
    if(low > high) return 0;
    if(x <= low) {
        return high - x; 
    }else if(x >= high) {
        return x - low;
    }else {
        return high - low + min(high - x, x - low);
    }
}

int main() {
    scanf("%d%d", &n, &x);
    map<int, int> counter;
    for(int i = 1; i <= n; i++) {
        int xi;
        scanf("%d", &xi);
        counter[xi]++;
    }
    int low = counter.begin()->first, high = counter.rbegin()->first;
    int ans = get(low, high);    // 所有苹果都要
    // 只收集n-1个苹果
    if(n == 1) {
        if(low != x) {
            ans = 0;
        }
    }else {
        auto l = counter.begin();
        if(l->second == 1 && x > l->first) {
            l++;
            ans = min(ans, get(l->first, high));
        }
        auto r = counter.rbegin();
        if(r->second == 1 && x < r->first) {
            r++;
            ans = min(ans, get(low, r->first));
        }
    }
    printf("%d\n", ans);
    return 0;
}