[Luogu4447] [AHOI2018初中组]分组
2024-09-03 22:25:54
题目描述
小可可的学校信息组总共有n 个队员,每个人都有一个实力值a[i]a[i]a[i]。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的nnn 个队员分成若干个小组去参加这场比赛。
但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队,于是要求分成的每个小组的队员实力值连续,同时,一个队不需要两个实力相同的选手。举个例子:[1,2,3,4,5][1, 2, 3, 4, 5][1,2,3,4,5]是合法的分组方案,因为实力值连续;[1,2,3,5][1, 2, 3, 5][1,2,3,5]不是合法的分组方案,因为实力值不连续;[0,1,1,2][0, 1, 1, 2][0,1,1,2]同样不是合法的分组方案,因为出现了两个实力值为1 的选手。
如果有小组内人数太少,就会因为时间不够而无法获得高分,于是小可可想让你给出一个合法的分组方案,满足所有人都恰好分到一个小组,使得人数最少的组人数最多,输出人数最少的组人数的最大值。
注意:实力值可能是负数,分组的数量没有限制。
输入输出格式
输入格式:
输入有两行:
第一行一个正整数n,表示队员数量。
第二行有n 个整数,第i 个整数a[i]表示第i 个队员的实力。
输出格式:
输出一行,包括一个正整数,表示人数最少的组的人数最大值。
输入输出样例
输出样例#1: 复制
模拟一下题意,先按照能力值排序,然后找前面是否有一队的最后一个人是$a[i]-1$,如果有多个队就插到长度最小的后面,如果没有就新开一队。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define reg register
inline int read() {
int res = ;char ch=getchar();bool fu=;
while(!isdigit(ch)) {if(ch=='-')fu=;ch=getchar();}
while(isdigit(ch)) res=(res<<)+(res<<)+(ch^), ch=getchar();
return fu?-res:res;
} int n;
int a[];
int cnt, ans = 1e9;
int lst[], len[]; int main()
{
n = read();
for (reg int i = ; i <= n ; i ++) a[i] = read();
sort(a + , a + + n);
for (reg int i = ; i <= n ; i ++)
{
bool Find = ;
int res = , mn = 1e9;
for (reg int j = ; j <= cnt ; j ++)
if (lst[j] == a[i] - and len[j] < mn) mn = len[j], res = j, Find = ;
if (!Find) lst[++cnt] = a[i], len[cnt] = ;
else lst[res] = a[i], len[res]++;
}
for (reg int i = ; i <= cnt ; i ++) ans = min(ans, len[i]);
cout << ans << endl;
return ;
}
最新文章
- js随笔
- 常见IE浏览器bug及其修复方案(双外边距、3像素偏移、绝对定位)
- [知识点]C++中的运算符
- [saiku] 集成单点登录
- c++迭代器(iterator)详解
- HDU 1051 - Rightmost Digit
- Matlab中取模(mod)与取余(rem)的区别
- form表单target的用法,实现无刷新提交页面
- 整理一些css在使用中的小技巧(进行中)
- JAVA判断32位还是64位,调用不同的DLL(转)
- Python自然语言处理学习笔记之性别识别
- MACOS关闭指定端口
- laravel中间件使用
- 洛谷P4778 Counting swaps 数论
- python远程连接windows
- 计算机名称改名之后,tfs连接问题
- 移动端和PC端页面常用的弹出层
- graph slam BACK END 相关技术资料收集
- mysql学习(4)python操作数据库
- Linq to Entity 动态拼接查询条件(重点是OR)