二分法解答

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N], b[N], s[N];  // a原数组，b去重后数组，s连续段长度
int sc;                // 连续段的个数

// 检查能否使每组人数至少为mid
bool check(int mid) {
    for (int i = 0; i < sc; i++)
        if (s[i] < mid) return false;  // 某段长度不足mid则失败
    return true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    sort(a, a + n);  // 排序
    
    // 去重
    int m = 0;
    b[m++] = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] != a[i-1]) b[m++] = a[i];
    
    // 划分连续段，记录每段长度
    sc = 0;
    int len = 1;
    for (int i = 1; i < m; i++) {
        if (b[i] == b[i-1] + 1) len++;      // 连续则长度+1
        else s[sc++] = len, len = 1;        // 断开则保存当前段，重置长度
    }
    s[sc++] = len;  // 保存最后一段
    
    // 二分答案：最大化最小人数
    int l = 1, r = n, ans = 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {  // 若mid可行，尝试更大
            ans = mid;
            l = mid + 1;
        } else {           // 若mid不可行，减小
            r = mid - 1;
        }
    }
    
    cout << ans;
}