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

· · 题解

这是一道贪心加排序（队列的题）（先大致聊聊贪心）

何为贪心？

所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似解。 

 用一句话来概括贪心就是从局部最优解推到全局最优解

解决贪心问题的基本思路

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的局部最优解合成原来问题的一个解。

算法分析

【适用问题】 具备贪心选择和最优子结构性质的最优化问题。

贪心选择：每次的选择可以依赖以前的选择，但不能依赖于后面的选择。

最优子结构：问题的整体最优解中包含着它子问题的最优解

下面进入正轨

但我第一次看到这道题时，想了想，还是很简单的，不就是排序，加贪心吗？ 于是下面为第一次代码。

#include<bits/stdc++.h>
using namespace std;
long long a[100000],n,ans=1,maxn;
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) 
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int j=1; j<=n; j++)
    {
    if(a[j]+1==a[j+1])
    {
    ans++;  
    }
    if(a[j]+1!=a[j+1])
    {
    maxn=ans;
    ans=1;  
    }
    }
    cout<<maxn;
}

其实就是将输入的排了个序然后输出能最小组有多少个，但是这个想法有点太简单了，因此才得了40分，原因是在分组的时候出了问题。于是我进行的下一次修改。

以下为第二次代码

#include<bits/stdc++.h>
using namespace std;
long long a[100005],n,ans=1,maxn;
int minn=199999999; 
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) 
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int j=1; j<=n; j++)
    {
    if(a[j]+1==a[j+1])
    {
    ans++;  
    }
    if(a[j]+1!=a[j+1])
    {
    maxn=ans;
    ans=1;  
    if(maxn<minn)minn=maxn;//这次的改动在这，进行了选择，输出最小组。
    }
    }
    cout<<minn;
}

但是，还是只有60分，我就在想暴力是不是偏离了正轨，然后我们机房的某位大佬跟我们讲了讲思路，其实贪心（二分答案）+队列才是正解。

把每一个组看成一个队列。我们只要关心的是队尾每次插入的元素是什么就行。将n个数排序，从头到尾扫一遍，每次扫到一个数，就看一看现有的组（队列）中有没有末尾是该数-1的，有就插入进去，该组数量+1。直到扫完，输出最小组数的长度。

每次选队列时，为了增高平均水平当然是加给最短的那个，如果没有符合要求的，新开一个队列。

于是我重新写了一遍

#include<bits/stdc++.h>
using namespace std;
int a[100005],n;
int cnt, minn=199999999;
int lst[100005],len[100005];
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)//将组的大小排列
    {
        bool find=0;
        int res=0,maxn=199999999;
        for (int j=1;j<=cnt;j++)//从最小组开始，一组一组的找，慢慢寻找最小值。
        if(lst[j]==a[i]-1&& len[j]<maxn)
        {
         maxn=len[j];
         res=j;
         find=1;
        }
        if(!find)//开队列进行查找。
        {
         lst[++cnt]=a[i];
         len[cnt]=1;
        }
        else
        {
         lst[res]=a[i];
         len[res]++;
        }
    }
    for(int i=1;i<=cnt;i++)
    minn=min(minn,len[i]);//进行比较看哪一种情况更小
    cout<<minn<<endl;
    return 0;
}

最后终于ac了这道题。下面是我的艰辛历程，希望大家可以早日AC，Thanks♪(･ω･)ﾉ。如果有好办法的，可以教教我这个蒟蒻。