P4447 [AHOI2018初中组]分组 （二分）------详解
小可可的学校信息组总共有n 个队员，每个人都有一个实力值a[i]a[i]。现在，一年一度的编程大赛就要到了，小可可的学校获得了若干个参赛名额，教练决定把学校信息组的nn 个队员分成若干个小组去参加这场比赛。
但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队，于是要求分成的每个小组的队员实力值连续，同时，一个队不需要两个实力相同的选手。举个例子：[1, 2, 3, 4, 5]是合法的分组方案，因为实力值连续；[1, 2, 3, 5]不是合法的分组方案，因为实力值不连续；[0,1,1,2]同样不是合法的分组方案，因为出现了两个实力值为1 的选手。
如果有小组内人数太少，就会因为时间不够而无法获得高分，于是小可可想让你给出一个合法的分组方案，满足所有人都恰好分到一个小组，使得人数最少的组人数最多，输出人数最少的组人数的最大值。
注意：实力值可能是负数，分组的数量没有限制。
输入格式输入有两行：
第一行一个正整数n，表示队员数量。
第二行有n 个整数，第i 个整数a[i]表示第i 个队员的实力。
输出一行，包括一个正整数，表示人数最少的组的人数最大值。
输入输出样例输入 #1
7
4 5 2 3 -4 -3 -5
输出 #1
3
题意： 这道题的大致意思就 给你一些 数字（有重复），然后让你给它们刚好分成一些组，当然要合理，合理就是每个组里面都是连续的数，然后还有一个条件就是 每个组里面的人数要尽量多，其实就是 叫你少分几个组，能两个组装下，就不要再搞一个小组，然后要你说出，这些组中 数的数量最小。
然后还有几点要求：
使得人数最少的组人数最多 ====> 是这样断句的 ： 使得 人数最少的组 人数最多
这个条件的意思就是每个组里面的人数要尽量多（人数最多），其实就是 叫你少分几个组，能两个组装下，就不要再搞一个小组
例如： 1 2 2 3 3 4 4 5 满足条件 分成 [ 1 2 3 4 5] 和 [2 3 4] 就够了，不要为了人数少二多开一个 变成 [1 2 3] ，[4 5] 和 [ 2 3 4]； 这么搞 还不如一个人一组； 出题人的意思就 这些数的 分法 其实都固定死的，只不过让你用手段找找这些分组中 ，人数最小的组的大小。
思路： 先排个序，然后依次给他们安排一下组，例如 该给 Ai安排一个组，就需要去看看已存在的组中有没有Ai 可以去的组，假设Qj组正好 当前最大为Ai-1, Ai 到Qj组，Qj组的大小就可以 +1 了,反之 如果没有，就需要新增加一个Q组，把Ai放进去当组头。n那么如何找到Qj,再用遍历，看下数据规模，肯定会 T, 怎么办，用二分查找优化一下找Qj的过程。详情看代码吧
这里整给二分查找优化优化（为啥可以用二分可以先想想，最后有说明）
题目链接： https://www.luogu.com.cn/problemnew/solution/P4447
AC代码：
#include
#include
#include
typedef long long int ll;
const int M=1e5+10;
using namespace std;
int main(){
ll n;
cin>>n;
ll a[M];
ll q[M]; //代表每一个组的状态，
//存放每个组（单调递增）当前组大的数（这个数基本就代表这个组的当前状态）+1，即能使得该组的单调性变长的数值。
// q[5]= 9 ==> 第5个分组 需要 9 来变长 现在为[... 6 7 8],需要来个 9
ll s[M];// 代表每一个组的里面数的数量；
ll t=0; // 代表当前已存在的组的数量； 0 代表有一个分组
for(int i=1;i>a[i];
sort(a+1,a+n+1); //从小到大排序
q[0]=a[1]+1;s[0]=1;//初始化
for(int i=2;i<=n;i++){//依次确认每个数属于那个组
int l=0,r=t;
while(l>1;
if(a[i]>=q[mid]) l=mid;
else r=mid-1;
}
if(q[l]!=a[i]) s[++t]=1,q[t]=a[i]+1;//需要开新组了
else s[l]++,q[l]++; //该组单调性可以加长了
}
int res=s[0];
for(int i=1;is[i]?res=s[i]:0;
cout<<res;
return 0;
}
二分优化说明：
因为：你处理数据是单调递增的，所以 你的每一个分组需要的 单调性变长的值 也会是单增
例如 当前 q[0]= 9， 当前安排的是
假设是 10 ，那么就需要新开一个q[1]，把 10 放进去[ 10 ] ,则q[1]=10+1=11;
假设是 8，说明是重复数据，也得新开一个q[1] ,把8 放进去 [ 8 ] 则 q[1]= 8+1=9;
假如是9 ，那就刚好，放进 q[0] ，q[0] 更新为 q[0] = 9+1= 10;
反正不会是比8 更小的数了（因为你安排的数已经是单调递增了）
所以， q数组的值都是严格递增的所以用二分查找优化。
作者：Five-菜鸟级
