题解 | #牛牛的朋友#

考察知识点：贪心

考虑两头牛时的情况，有以下 4 种移动方式：

1. 两头牛同时向左移动：距离不变
2. 两头牛同时向右移动：距离不变
3. 左边的牛向左移动，右边的牛向右移动：距离增大
4. 左边的牛向右移动，右边的牛向左移动：距离可能减小

其中前两种情况对答案没有影响，第三种情况可以直接忽略，第四种情况需要考虑。

推广到 n 头牛，可以知道最优的情况只会出现在「所有牛都往一个方向移动」或「靠左的牛往右边移动，靠右的牛往左边移动」这两种移动方法中。

因此，用变量 ans 记录初始距离（也即所有牛往同一方向移动的距离），循环枚举牛群的分界点，比较记录最优的距离，即为答案。

时间复杂度：$O(n\log n)O(n\; \backslash log\; n)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n, x;
    cin >> n;
    vl p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    cin >> x;
    sort(p.begin(), p.end());
    ll l = p[0], r = p[n - 1];
    ll ans = r - l;
    for (int i = 0; i < n - 1; i++)
    {
        l = min(p[i + 1] - x, p[0] + x);    // i: 1 ~ n
        r = max(p[i] + x, p[n - 1] - x);    // i: 0 ~ n-1
        ans = min(ans, r - l);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}