泊头做网站的有哪些,长安高端装备网站设计公司,中国建筑工程总公司招聘,重庆专业网站建设首页排名贪心没套路果真如此。
题目描述
小可可的学校信息组总共有 n 个队员#xff0c;每个人都有一个实力值 ai。现在#xff0c;一年一度的编程大赛就要到了#xff0c;小可可的学校获得了若干个参赛名额#xff0c;教练决定把学校信息组的 n 个队员分成若干个小组去参加这场…贪心没套路果真如此。
题目描述
小可可的学校信息组总共有 n 个队员每个人都有一个实力值 ai。现在一年一度的编程大赛就要到了小可可的学校获得了若干个参赛名额教练决定把学校信息组的 n 个队员分成若干个小组去参加这场比赛。
但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队于是要求分成的每个小组的队员实力值连续同时一个队不需要两个实力相同的选手。举个例子[1,2,3,4,5] 是合法的分组方案因为实力值连续[1,2,3,5] 不是合法的分组方案因为实力值不连续[0,1,1,2] 同样不是合法的分组方案因为出现了两个实力值为 1 的选手。
如果有小组内人数太少就会因为时间不够而无法获得高分于是小可可想让你给出一个合法的分组方案满足所有人都恰好分到一个小组使得人数最少的组人数最多输出人数最少的组人数的最大值。
注意实力值可能是负数分组的数量没有限制。
输入格式
输入有两行
第一行一个正整数 n表示队员数量。 第二行有 n 个整数第 i 个整数 ai 表示第 i 个队员的实力。
输出格式
输出一行包括一个正整数表示人数最少的组的人数最大值。
输入输出样例
输入 #1复制
7
4 5 2 3 -4 -3 -5
输出 #1复制
3说明/提示
【样例解释】 分为 2 组一组的队员实力值是 {4,5,2,3}一组是 {−4,−3,−5}其中最小的组人数为 3可以发现没有比 3 更优的分法了。
【数据范围】
对于 100% 的数据满足1≤n≤100000∣ai∣≤109。
本题共 10 个测试点编号为 1∼10每个测试点额外保证如下
测试点编号数据限制1∼2n≤6,1≤ai≤1003∼4n≤1000,1≤ai≤105 且 ai 互不相同5∼6n≤100000,ai 互不相同7∼8n≤100000,1≤ai≤10^59∼10n≤100000,−10^9≤ai≤10^9 思路
从小到大排序每组当出现不连续的数或前一个的个数比后一个的个数多时结束。
第二个是为什么
我想的是你多了可以给前面的组但你少了你若想向前方靠那你前面比你多的数和后面的数会因你而分开罪人若想当头和后面的在一起那前面多的数就会…… 代码
//忘记 2 2 3 3的情况
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includeiostream
#includebits/stdc.h
using namespace std;
int n, a[100005], m 1;
int min0 9999999;
struct s {int i, w;
}b[100005];
void xunhuan(int i, int j) {//当后面的数个数没前面多时||断了结束int z i;z;while (b[z].i 1 b[z 1].i z 1 j) {if (b[z].w b[z 1].w) {b[z].w--;m;z;}else {b[z].w--;m;break;}}
}
int main(){cin n;for (int i 0; i n; i) {cin a[i];}//输入数sort(a, a n);//排序也可以用我之前写的归并排序int j 0;for (int i 0; i n; i) {//将相同的合并if (i 0) {b[j].i a[i];b[j].w 1;}else {if (b[j].i a[i]) {b[j].w;}else {b[j].i a[i];b[j].w 1;}}}m 1;for (int i 0; i j; i) {if (b[i].i 1 b[i 1].ii1j) {if(b[i1].w1) {m;}//连续且单一else {while(b[i 1].w ! 1){//不但一防止该数的数量超过3xunhuan(i,j);min0 min0 m ? m : min0;m 0;}m 1;}}else {//不连续归零min0 min0 m ? m : min0;m 1;}}cout min0 endl;return 0;
}
你可以用c来写但归并手写有点多所以偷个懒
