P4447AHOI2018初中组分组两分——详细讲解

Estimated read time 1 min read

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

7
4 5 2 3 -4 -3 -5

 

输出#1

3

 

分组非主流超长_超长情侣分组一男一女_QQ超长分组/

题意:这道题的大体意思是给你一些数字(有重复),然后要求你把它们分成几组。 当然,必须是合理的。 合理是指每组包含连续的数字,还有一个条件是指每组的人数应尽可能多。 事实上,这意味着你们被分成了更少的组。 如果您可以组合两个,则不应组成另一个组,然后系统会要求您说出这些组中最小的数字。

然后还有几个要求:

让人数最少的小组人数最多====>这句话是这样分解的:让人数最少的小组人数最多

这个条件意味着每组的人数应该尽可能多(人数最多)。 事实上,这意味着你应该分成更少的组。 如果您可以聚集两个,则不应再组成另一个小组。

例如: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){ mid="(l+r+1)" int="" (去了刚好可以增加该组的长度)="" 当前数该去的组="" 在所有已存在的组里面找到="" 通过二分方法="">>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; code="" }<="" 0;="" return=""></res;></r){>

 

  
二进制优化指令:

  
因为:你处理的数据是单调递增的,所以你每个组所需的单调可变长度值也会单调递增

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

You May Also Like

More From Author