题意简化
求一种分配方案：
- 最大化队伍总数；
- 在满足 1 的情况下最小化最多人的队伍人数。
题目思路
由于本题目的数据量高达 \(10^6\)，且贪心算法也许不成立，所以需要考虑 \(n\log n\) 的算法！
具体的，对于一个人的需求 \(a_i\)，如果小于 \(a_i\) 的数先被选走，那么 \(a_i\) 可能问题：
不存在人数为 \(a_i\) 的团队（答案并非最优）
证明：
3
1
2
3
1 3
那么，由于上述原因，要使得存在 \(n\log n\) 算法就务必需要满足无后效性。
故以使用动态规划与二分答案解答。
我们首先应该对 \(a_i\) 排序，以消除后效性！
由于 1 是必要条件，所以通过动态规划队伍总量的最大值，然后使用二分找到最小的队伍人数；
那么动态转移方程成了必不可缺的内容！
动态转移方程：
对于每个 \(a_i\) 有两种可能：
- 被选；
- 选择。
如果是被选：
则代表 \(a_i\) 处于队伍中间，则 \(a_i\) 团队的起始人任然不变，即 \(last[i]=last[i-1]\)；
如果是选择：
则代表自己是对于开头，即 \(last[i]=i\)，并更新 DP 数组的答案。
此题方程定义参考沈子扬同学的定义。
当然，这样定义不便于代码的撰写，于是我们将操作 2 提前一位，即在原选择的情况下自己是团队的最后一位！
思路结。
HACK 补充：
10
3 3 3 3 3 4 4 4 4 4
2 5
6
1 1 3 3 3 3
3 4
From Discuss!
AC Code：
#include<bits/stdc++.h>
using namespace std;
int n,a[1000010],dp[1000010],last[1000010];
int work(int mid)
{
memset(dp,-1,sizeof(dp));
memset(last,0,sizeof(last));
dp[0]=0;
for(int i=1;i<=n;i++)
{
if(a[i]<=i && dp[last[i-a[i]]]>=0 && last[i-a[i]]+mid>=i)dp[i]=dp[last[i-a[i]]]+1;
if(dp[i]>=dp[last[i-1]])last[i]=i;
else last[i]=last[i-1];
}
return dp[n];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=0,r=n+1,num=work(n);
while(r-l>1)
{
int mid=l+(r-l)/2;
if(work(mid)==num)r=mid;
else l=mid;
}
printf("%d %d",num,r);
return 0;
}