[AHOI2018初中组]分组---贪心算法

贪心没套路果真如此。 题目描述

小可可的学校信息组总共有 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 #include<stdio.h> #include<iostream> #include<bits/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].i&&i+1<=j) { if(b[i+1].w==1) { m++; }//连续且单一 else { while(b[i + 1].w != 1){//不但一，防止该数的数量超过3 xunhuan(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来写，但归并手写有点多，所以偷个懒