USACO 2019 US Open Contest, Silver

T1.Sleepy Cow Herding

这道题是个结论题

1. 我们先找出最大连续子段，如果全部连续，则不用计算
2. 求最大值，就尽量把所有的空位都踩一遍，我们每次操作把第 \(n\) 号奶牛往第 \(1\) 头奶牛和第 \(n-1\) 头奶牛之间或者把第一头奶牛往第 \(2\) 头奶牛和最后一头奶牛之间移动，最大的空隙再减去 \(n - 2\) 就好了，因为向两段之间空隙只间移动的时候，那两端是不用挪动的。
3. 求最小值，首先我们知道所有奶牛连续到一起，长度一定为 \(n\) ，所以我们只需要找一段最开始长度为 \(n\) ，且奶牛最多的线段，然后再把其他端点上面的奶牛放在里面就可以。然后答案就为 \(n\) 减去包含的最多的奶牛数。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N];
int main()
{
    freopen("file herding.in", "r", stdin);
    freopen("file herding.out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    int cnt = 0, now = 1;
    for (int i = 1; i < n; i++)
    {
        if (a[i] == a[i - 1] + 1) //说明连续
            now++;
        else
            now = 1;
        cnt = max(cnt, now); //求最长连续段
    }
    if (cnt == n) //全部连续,不用计算
    {
        cout << 0 << endl << 0;
        return 0;
    }
    int ans = 0x3fffffff;
    int l = 0, r = 0;
    while (l < n)
    {
        while (r < n && a[r] <= a[l] + n - 1)
            r++;
        ans = min(ans, n - (r - l)); //找连续空位区间
        l++;
    }
    if (cnt == n - 1) // 如果有n-1头牛连续，那么中间就不会有空位
    {
        ans = 2;
        if (a[0] == a[1] - 2 || a[n - 1] == a[n - 2] + 2) //直接让某一位跳到他们之间即可
            ans = 1;
    }
    cout << ans << endl;
    ans = max(a[n - 2] - a[0], a[n - 1] - a[1]) - n + 2;
    cout << ans << endl;
    return 0;
}