Luogu P4447 [AHOI2018初中组]分组

题目链接：传送门

将$n$个可重复的整数分为$m$组，每组中的数必须连续且不重复，使人数最少的组人数最多。
两个最值肯定第一想到二分，每次二分出一个值，判断在这个值为答案的前提下能否完成分组。
在思考判别函数时发现没有必要二分，单独依靠人数底线也并不能得到最优解，通过贪心就可以直接得到答案。

先将这些数从小到大排序，对每个数进行分组，$group[i]$表示第$i$组的末尾的数，可见每组内的数是升序的。
对于一个数$a[i]$，遍历现有的所有组，如果有一个组的末尾的数$group[i]=a[i]-1$，则表示这个数可以接在这组的队尾。
但这样并不能保证最优解，那我们添加一个条件，将这个数加在长度最短的队的队尾，即可保证最优。

#include <bits/stdc++.h>
#define A 100010using namespace std;
int n, a[A];
int num, size[A], group[A];int main(int argc, char const *argv[]) {cin >> n;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++) {int size_min = INT_MAX, pos = 0; bool flag = 0;for (int j = 1; j <= num; j++)if (group[j] + 1 == a[i] and size[j] < size_min)pos = j, flag = 1, size_min = size[j];if (flag) size[pos]++, group[pos] = a[i];else group[++num] = a[i], size[num] = 1;}int ans = INT_MAX;for (int i = 1; i <= num; i++) ans = min(ans, size[i]);cout << ans << endl;
}