P4447【AHOI2018初中组】小组题目说明
小可可的学校信息组一共有n名队员，每个队员的实力值为a[i]a[i]。 现在，一年一度的编程大赛即将到来，肖可可所在的学校已经获得了几个参赛名额。 教练决定将学校信息队的n名队员分成几组参加本次比赛。
不过每个玩家都不愿意和一个实力与自己差距太大的玩家组队，所以要求每个组的实力是连续的。 同时，一支球队并不需要两名实力相同的球员。 例如：[1,2,3,4,5]是合法的分组方案，因为强度值是连续的； [1,2,3,5]不是合法的分组方案，因为强度值是不连续的； [0, 1,1,2] 也不是合法的分组方案，因为有两个玩家的强度值为 1。
如果一个组的人太少，你就会因为时间不够而拿不到高分，所以小可可要你想出一个合法的分组方案，让每个人都能准确地分到一组，这样人数最少的小组人数最多。 ，输出人数最少的组中的最大人数。
注意：强度值可以为负数，组数没有限制。
输入格式
输入有两行：
第一行是一个正整数n，代表玩家的数量。
第二行有n个整数，第i个整数a[i]代表第i个玩家的实力。
输出格式
输出一行，其中包含一个正整数，表示人数最少的组中的最大人数。
输入和输出样本
输入#1
74 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作为Q组的大小。组长。 n那么怎么找到Qj，然后用遍历，看看数据大小，肯定是T，怎么办，用二分查找优化找Qj的过程。具体看代码
这里是二分查找的优化和优化（大家可以先想一下为什么可以用二分查找，最后会有解释）
主题链接：
交流代码：
#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<=n;i++)cin>>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<r){ //通过二分方法 在所有已存在的组里面找到 当前数该去的组 （去了刚好可以增加该组的长度） int mid=(l+r+1)>>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;i<=t;i++) res>s[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数组的值是严格递增的，所以采用二分查找的方式进行优化。