思路：排序+双指针

其实就是找到一段连续的数值，有点类似 LeetCode 2134，就是多了一个排序的过程，比如[1,5]这个区间，中间隔了3个数字，那么就需要执行3个操作，才可以保证这个区间是一个连续的区间，对应的操作次数就是n-(r-l+1)，如果区间所需要的数字比n还大，说明不满足条件，需要l指针右移。

代码

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1E5+10;
int n,w[N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>w[i];
    sort(w,w+n);
    int res=INT_MAX;
    for(int l=0,r=0,sum=0;r<n;r++)
    {
        while(w[r]-w[l]+1>n)l++;
        res=min(res,n-(r-l+1));
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }
        Arrays.sort(w);

        int res = Integer.MAX_VALUE;
        for (int l = 0, r = 0, sum = 0; r < n; r++) {
            while (w[r] - w[l] + 1 > n) {
                l++;
            }
            res = Math.min(res, n - (r - l + 1));
        }
        System.out.println(res);
    }
}

Python

n = int(input())
w = list(map(int, input().split()))
w.sort()

res = float('inf')
l = 0
for r in range(n):
    while w[r] - w[l] + 1 > n:
        l += 1
    res = min(res, n - (r - l + 1))

print(res)

题目内容

小红 $4*10^9+1$ 个羊圈，这些羊圈的编号依次为 $-2*10^9～2*10^9$，有的羊圈有若干只羊，有的是空羊圈。现在，小红想将一些羊圈中的羊赶入某些羊圈杯中，以此来重新排列这些羊圈的次序。最终让所有的羊最终都圈在 $n$ 个不同的羊圈中，并且这 $n$ 个羊圈编号依次相邻。为了防止羊羊逃跑，对于每一次转移，小红只能将任何一个羊圈中的所有羊全部赶入任何一个空的羊圈中。

求最少的转移次数？

输入描述

第一行输入有羊的羊圈的数量 $N$。

随后 $N$ 行，输入N个有羊的羊圈的编号 $a_i$。

保证没有两个 $a_i$是相同的。

$1\leqslant N\leqslant 10^5$

$-2*10^9\leqslant a_i\leqslant 2*10^9$

输出描述

输出羊的最少的转移次数使得有羊的羊圈按照顺序排列。

样例

样例1

输入

4
13 12 11 14

输出

0

样例解释

现在，在11,12,13,14号羊圈中有羊羊了，所以不需要调整了。

样例2

输入

5
2 0 -1 3 6

输出

1	

样例解释

现在在-1,0,2,3,6中有羊，因此，1号羊圈没有羊，因此可以将6号羊圈中的羊全部赶入1号羊圈中，这样有羊的羊圈为-1,0,1,2,3

样例1

输入

5
2 -4 -1 3 6

输出

2

样例解释

现在在-4,1,2,3,6中有羊，可以将-4号羊圈中的羊赶入入0号羊圈，将6号羊圈中的羊赶入1号羊圈，这样，-1,0,1,2,3均有羊。