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的过程。详情看代码吧

这里整给二分查找优化优化（为啥可以用二分可以先想想，最后有说明）

题目链接： 登录 - 洛谷

AC代码：

#include <iostream>#include <algorithm>#include <cstring>typedeflonglongintll;
constintM=1e5+10;
usingnamespacestd;
intmain(){
lln;
cin>>n;
lla[M];
llq[M]; //代表每一个组的状态，//存放每个组（单调递增）当前组大的数（这个数基本就代表这个组的当前状态）+1，即能使得该组的单调性变长的数值。// q[5]= 9  ==> 第5个分组 需要 9 来变长 现在为[... 6 7 8],需要来个 9 lls[M];// 代表每一个组的里面数的数量； llt=0; //  代表当前已存在的组的数量； 0 代表有一个分组for(inti=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1); //从小到大排序q[0]=a[1]+1;s[0]=1;//初始化 for(inti=2;i<=n;i++){//依次确认每个数属于那个组   intl=0,r=t;
while(l<r){ //通过二分方法 在所有已存在的组里面找到 当前数该去的组 （去了刚好可以增加该组的长度） intmid=(l+r+1)>>1;
if(a[i]>=q[mid]) l=mid;
elser=mid-1;
            }   
if(q[l]!=a[i]) s[++t]=1,q[t]=a[i]+1;//需要开新组了 elses[l]++,q[l]++;   //该组单调性可以加长了            } 
intres=s[0]; 
for(inti=1;i<=t;i++) res>s[i]?res=s[i]:0;
cout<<res;
return0;
}

二分优化说明：

因为：你处理数据是单调递增的，所以 你的每一个分组需要的 单调性变长的值 也会是单增

例如 当前 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数组的值都是严格递增的所以用二分查找优化。