[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∼2	n≤6,1≤ai​≤100
3∼4	n≤1000,1≤ai​≤105 且 ai​ 互不相同
5∼6	n≤100000,ai​ 互不相同
7∼8	n≤100000,1≤ai​≤10^5
9∼10	n≤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){//不但一，防止该数的数量超过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来写，但归并手写有点多，所以偷个懒