题解 | #牛牛的朋友#

贪心这种基本是靠猜猜的，思路要证明的话反而不好搞：

对于这道题，我们要做的就是“收缩”整个区间，同时从样例可以看出可能有内部的元素变成了新的左边与右边，不能只跟踪原来的两个maxmin元素。主要是我老是在犹豫怎么才能拿到不同转移状态下的最右边/左边的元素，跟在写动态规划似的这里的贪心思路是：一定存在一个分界点：使得左边的全部向右，右边的全部向左，来这样收束整个区间（很抽象吧，那肯定是先猜后面再来证明合理性）

假设在从左向右走已经有牛向左走，但是之后有牛向右走。首先这肯定没法减少右边，对于左边：肯定没法做到“穿透”：肯定不如你上一个走左边的，人家一开始位置都比你左你还不去追。

说人话就是第i个元素向左走了，后面所有元素对于右边界都没有贡献了，右边同理。这样一来，对于每一个分界点，我们可以在O(1)内完成查询左右的操作。具体实现就是：

for(int r = 1;r < n;r++)//第i个元素开始右移，排除全左全右的情况
{
    int leftbound = min(cowp[0] + x,cowp[r] - x);
        
    int rightbound = max(cowp[r - 1] + x,cowp[n - 1] - x);
        
    if(rightbound - leftbound < ans)
    {
        ans = rightbound - leftbound;
    }
}

对应最左边和最右边的元素要么是原来的，要么是另一个区间的第一个。当然也有可能就整体全部向一个方向动，为了防止负数索引问题，需要提前排除。赋值给ans当初始值就OK了

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
     
    int n;
     
    cin>>n;
     
    vector<int> cowp(n,0);
     
    int maxp = LLONG_MIN;
     
    int minp = LLONG_MAX;
     
    for(int r = 0;r < n;r++)
    {
        cin>>cowp[r];
    }
     
    sort(cowp.begin(),cowp.end());
     
    int x;
     
    cin>>x;
     
    int ans = (*max_element(cowp.begin(),cowp.end()) - *min_element(cowp.begin(),cowp.end()));
     
    for(int r = 1;r < n;r++)//第i个元素开始右移，排除全左全右的情况
    {
        int leftbound = min(cowp[0] + x,cowp[r] - x);
         
        int rightbound = max(cowp[r - 1] + x,cowp[n - 1] - x);
         
        if(rightbound - leftbound < ans)
        {
            ans = rightbound - leftbound;
        }
    }
     
    cout<<ans<<endl;
     
    return 0;
}

感觉贪心题就是个猜猜思路的过程，合理性的证明是后面实现时候的事情。但是做题见得多肯定比少要好，只能这样想了