[AHOI2018初中组] 分组

题目链接:

[AHOI2018初中组] 分组 - 洛谷


题目描述

小可可的学校信息组总共有 $n$ 个队员,每个人都有一个实力值 $a_i$ 。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的 $n$ 个队员分成若干个小组去参加这场比赛。

但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队,于是要求分成的每个小组的队员实力值连续,同时,一个队不需要两个实力相同的选手。举个例子:[1, 2, 3, 4, 5] 是合法的分组方案,因为实力值连续;$[1, 2, 3, 5]$ 不是合法的分组方案,因为实力值不连续;$[0, 1, 1, 2]$ 同样不是合法的分组方案,因为出现了两个实力值为 $1$ 的选手。

如果有小组内人数太少,就会因为时间不够而无法获得高分,于是小可可想让你给出一个合法的分组方案,满足所有人都恰好分到一个小组,使得人数最少的组人数最多,输出人数最少的组人数的最大值。

注意:实力值可能是负数,分组的数量没有限制。

输入格式

输入有两行:

第一行一个正整数 $n$,表示队员数量。

第二行有 $n$ 个整数,第 $i$ 个整数 $a_i$ 表示第 $i$ 个队员的实力。

输出格式

输出一行,包括一个正整数,表示人数最少的组的人数最大值。

样例 #1

样例输入 #1

text
1
2
7
4 5 2 3 -4 -3 -5

样例输出 #1

text
1
3

提示

【样例解释】
分为 $2$ 组,一组的队员实力值是 ${4, 5, 2, 3}$,一组是 ${-4, -3, -5}$,其中最小的组人数为 $3$,可以发现没有比 $3$ 更优的分法了。

【数据范围】

对于 $100%$ 的数据满足:$1\leq n\leq 100000$,$|a_i|\leq10^9$。

本题共 $10$ 个测试点,编号为 $1\sim10$,每个测试点额外保证如下:

测试点编号 数据限制
$1\sim2$ $n\leq 6, 1\leq a_i \leq 100$
$3\sim4$ $n\leq 1000, 1\leq a_i\leq 10^5$ 且 $a_i$ 互不相同
$5\sim6$ $n\leq 100000$, $a_i$ 互不相同
$7\sim8$ $n\leq 100000, 1\leq a_i \leq10^5$
$9\sim 10$ $n\leq 100000, -10^9 \leq a_i \leq 10^9$

题解

对应于前两个测试点,由于没有重复元素,所以我们可以直接将数组排序,然后遍历判断。

对于后面的测试点,我们可以模仿之前的思路,同样先进行排序,与之前不同的是,我们需要考虑这些重复的元素。例如 $[1,2,2]$ ,由于是有序的,所以相同的元素不能放在前面一组内,显然应该放在应该新的组内,也就是这个会有两个分组,答案为 $1$ 。那么如果后面还有元素,比如 $3$ ,我们需要加入额外的判断。与两个测试点对比,对于前两个测试点,由于不存在相同的元素,是能放就放的原则。对于同元素的测试点,先让将 $3$ 放在较小的集合内更好,也就是有多个集合能放时每次放小的集合内,也就是贪心的思想。

下面是完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

int a[100005];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main()
{
int n;
n=read();
for (int i=0;i<n;i++)
{
a[i]=read();
}
sort(a,a+n);
deque<int> q[n];
int k=0;
for (int i=0;i<n;i++)
{
int k1=-1;
int len=100000;
for (int j=max(0,k-100);j<k;j++)
{
if (q[j].back()==a[i]-1 && q[j].size()<len) k1=j;
}
if (k1<0)
{
q[k].push_back(a[i]);
k++;
}
else
{
q[k1].push_back(a[i]);
}
}
int sum=100000;
for (int i=0;i<k;i++)
{
if (q[i].size()<sum) sum=q[i].size();
}
cout<<sum;
return 0;
}

[AHOI2018初中组] 分组
https://serendipity565.github.io/posts/e4de1b3aaa63/
作者
Serendipity
发布于
2024年7月3日
许可协议
BY-SERENDIPITY565