洛谷-P5541 Sleepy Cow Herding S

Sleepy Cow Herding S

Sleepy Cow Sorting 的升级版，从 \(3\) 头牛变成 \(n\) 的情况

分类讨论 + 双指针

• 先把答案本就连续的特判丢掉

• 最大值

最大值就尽量把每个空位都踩一遍，模拟一下会发现，第一跳的空隙一定没办法踩到，因此考虑两边第一跳谁跳的短，就从哪边开始

• 最小值

1. 考虑枚举答案所在的连续 \(n\) 个位置，假设枚举的这个区间外的牛，都可以跳进来，则答案为 \(n - cnt_{lr}\)

显然可以转化成为：找到一个长度为 \(n\) 的连续区间，使得牛尽可能多，双指针处理即可

2. 会有不满足条件 \(1\) 的情况，也就是在区间外的牛没办法跳进来，这种情况只有 \(n - 1\) 头牛连续才会出现

   1. 类似于 5 8 9 10 的情况，区间在 \([7, 10]\) 为最优，可以让 \(10\) 跳到 \(6\)，留个位置给 \(5\) 跳到 \(7\)，总共 \(2\) 跳

   2. 类似于 6 8 9 10 的情况，区间在 \([7, 10]\) 为最优，直接让 \(10\) 跳到 \(7\) 即可，即唯一一个不连续的牛，距离连续的牛的距离为 \(2\) 的情况，只需要 \(1\) 跳

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    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(now, cnt);
    }
    if(cnt == n) {cout << "0\n0\n"; 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)
    {
        ans = 2;
        if(a[0] == a[1] - 2 || a[n - 1] == a[n - 2] + 2) ans = 1;
    }
    cout << ans << endl;
    ans = a[n - 1] - a[0] - 1;
    ans -= n - 2;
    ans -= min(a[1] - a[0], a[n - 1] - a[n - 2]) - 1;
    cout << ans << endl; 
    return 0;
}