P4447 [AHOI2018初中组]分组 (二分)——详解

                            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-菜鸟级

相关推荐

参考原子哥,易于理解

STM32f10x 外部中断及中断分组

洛谷P2678 跳石头 二分

程序员面试金典 – 面试题 10.03. 搜索旋转数组(二分查找)

在这里插入图片描述

小白终是踏上了这条不归路—-小文的mysql学习笔记(5)—-分组查询