题目描述

Farmer John的 N 头奶牛总是会迷路走到农场上遥远的地方去！

他需要你帮助将她们一起赶回来。

农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。

这 N 头奶牛现在正位于不同的整数位置，Farmer John想要移动她们，使得她们占据相邻的位置（例如，位置 3、4、5、6、7、8）。

不幸的是，奶牛们现在很困，Farmer John要让她们集中精力听从命令移动并不容易。

任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。

当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。

可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到 N 个相邻位置所进行的移动次数的最小和最大可能值。

输入样例

3
7
4
9

输出样例

1
2

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    //缺口在边缘的情况
    if(a[n-2]-a[0]==n-2&&a[n-1]-a[n-2]>2)//1 2 3 6
    {
        cout<<2;
    }
    else if(a[n-1]-a[1]==n-2&&a[1]-a[0]>2)//1 4 5 6
    {
        cout<<2;
    }else
    {
        int x=0;
        for(int i=0,j=0;i<n;i++)//枚举i为左端点,j为右端点的区间
        {
            while(j<n-1&&a[j+1]-a[i]<=n-1) //没有越界且区间长度小于等于n，增加已有的点的数目
                j++;
            x=max(x,j-i+1); //得到区间长度小于等于n的已有点的数目的最大值
        }
        cout<<n-x;
    }
    cout<<endl;
    cout<<max(a[n-2]-a[0],a[n-1]-a[1])-(n-2);//移动最左边的点和最右边的点的需要的步数的最大值
    return 0;
}