题解 P5541 【 [USACO19FEB]Sleepy Cow Herding】

· · 题解

居然还有橙题没有题解？？？虽然我觉得这道题不属于橙题（可能我太弱了） 不过本体还是很有思维的（我没有夸自己）

最小值：

首先，我们应该知道，解决问题后奶牛的长度最少应该是N，所以，对于一段长度为N的区域，如果我们要想把所有奶牛都移到里面，至少要奶牛总数N减去这段区域里面本来就有的奶牛。

那么，怎么可以是答案最小呢，只要找到一段长度为N的区域里面本来就有的奶牛数量最多就行了（本来就在里面，你还移动他？？？）

int ansmin(){
    if((a[n-2]-a[0]==n-2&&a[n-1]-a[n-2]>2)||(a[n-1]-a[1]==n-2&&a[1]-a[0]>2))
        return 2;
    int j=0;
    for(int i=0;i<n;i++){
        while(j<n-1&&a[j+1]-a[i]<=n-1)
            j++;
        x=max(x,j-i+1);
    }
    return n-x;
}

最大值：

其实最大值要比最小值好求（从代码长度就知道了）

最多就是一个一个移动，先判断 第一个到倒数第二个 与 第二个到倒数第一个 那个长（因为你要最大值嘛），在减去N-2。

考虑A[1]-A[0]和A[N-1]-A[N-2]的两个端点间隙。我们的第一步必须“牺牲”其中的一个缺口，这就意味着我们不能把任何一头牛移到这个缺口中。然而，除了这一个缺口之外，我们还可以确保一头奶牛落在我们队列中A[0]和A[N-1]之间的每一个空白处。我们可以通过在排序左侧有两个相邻牛的状态和排序右侧有两个相邻牛的状态之间切换来实现这一点。

int ansmax(){
    return max(a[n-2]-a[0],a[n-1]-a[1])-n+2;
}

（我可能语文不好，你要没看懂，你就在看看代码，模拟一下样例，可能就理解了）

上代码！！

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> 
using namespace std;

int n,a[100005],x=0;

int ansmin(){
    if((a[n-2]-a[0]==n-2&&a[n-1]-a[n-2]>2)||(a[n-1]-a[1]==n-2&&a[1]-a[0]>2))
    //特判，如果a[n-2]到a[0]或a[n-1]到a[1]的间隔正好是N-2，而且a[n-1]到a[n-2]或a[1]到a[0]的距离大于2
    //那么只要a[n-1]和a[n-2]或a[1]和a[0]各移动一次就可以了（你可以模拟试一试）
        return 2;
    int j=0;
    for(int i=0;i<n;i++){
        while(j<n-1&&a[j+1]-a[i]<=n-1)
            j++;
        x=max(x,j-i+1);
    }
    return n-x;
}

int ansmax(){
    return max(a[n-2]-a[0],a[n-1]-a[1])-n+2;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    printf("%d\n%d\n",ansmin(),ansmax());
    return 0;
}