题解 P4447 【[AHOI2018初中组]分组】

· · 题解

这道题做法很多，比如贪心啊，二分答案（确实可以，有人A了）啊，差分啊，集思广益，群策群力（不是指比赛）。。

本蒟蒻用的是挖矿火车法模拟，这里不贴代码了。

我来介绍一个效率很高，而且很不错的方法。

把每一个组看成一个队列。我们只要关心的是队尾每次插入的元素是什么就行。

将n个数排序，从头到尾扫一遍，每次扫到一个数，就看一看现有的组（队列）中有没有末尾是该数-1的，有就插入进去，该组数量+1。直到扫完，输出最小组数的长度。

没了？

不。每次选队列时，也许有很多符合要求的，但是选哪一个呢？不好好考虑这个会40的！

当然是加给最短的那个啦！挺高平均水平嘛！（手动滑稽） 如果没有符合要求的，新开一个队列。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,a[100005];
struct node{
    int num;
    int b;
}ans[100005];
int l=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
            bool ok=false;
            for(int j=l;j;j--)//枚举现有的队列，后面的长度比较小
            {
                if(ans[j].b==a[i]-1)
                {
                    ok=true;
                    ans[j].num++;
                    ans[j].b++;
                    break;
                }
            }
            if(!ok){
                l++;
                ans[l].b=a[i];//每组记录最后一个就行了
                ans[l].num++;
            }

    }
    int ans1=ans[1].num; 
    for(int i=2;i<=l;i++){
        ans1=min(ans1,ans[i].num);
    }
    cout<<ans1<<endl;
    return 0;
}

注明代码出处：@小松鼠cxr