P11455 [USACO24DEC] Cowdepenence G

· · 题解

G 组练习总结#14

Platinum 组开题，三道 Benq，两眼一黑，不省人事。

那就来研究 Gold 组吧。

题目大意

FJ 的奶牛们正在交朋友，她们希望组成一个个小组促进感情。

具体来说，FJ 拥有 N(N\le 10^5) 个奶棚，i(i\le N) 号奶棚里有一只品种为 a_i(a_i\le N) 的奶牛，两个奶棚的距离为编号相减。

奶牛很高傲，只愿意和自己品种相同的奶牛做朋友，同时，为了方便交流，朋友之间的距离不能太远（可能取决于奶牛的嗓门大小吧）。

为了方便管理，FJ 规定奶牛们应组成尽可能少的小组。

现在，他想知道，对于每一个最大交流距离 x(1\le x\le N)，最少需要分多少个小组？

解题思路

我们首先可以想一些题目的性质，一个小组必定在一段长度小于交流距离的区间里，否则不优。

其次，当我们确定了左端点时，右端点肯定是尽可能大，尽量涵盖更多奶牛。

如果一头奶牛已经超出了左端点的交流范围，新开一组。

暴力

有了这上面的性质，我们可以写出最基础的暴力了，枚举交流距离，扫一遍所有奶牛，超出范围就新开一组，时间复杂度 \Theta(N^2)。

这道题目的另外两个部分分很有引导性，解决它们对得出正解有很大帮助。

Subtask 1：品种数量不超过 10

既然，品种数量这么少，我们可以考虑对每一个品种单独处理。

思考一下，如果当前的交流距离为 x，这个品种的奶牛分组数量不可能大于 \lceil\frac{N}{x}\rceil 个，因为塞不下更多长度为 x 的区间了。

我们找到第一个左端点编号 pos，然后在 pos+x 之后找到下一个最近的，设为第二个左端点，同时组数加一。

因为分组数量有上限，这种跳跃的操作不会超过 \lceil\frac{N}{x}\rceil 次。

根据调和级数 \sum_{x=1}^N\frac{N}{x}\approx N\ln N，外加一个 10 （取决于品种数）的常数，复杂度 \Theta(N\ln N)。

跳跃操作可以通过记录数组 e 完成，e_i 表示 i 之后最近的这种品种奶牛的编号。

Subtask 2：每个品种的奶牛数量不超过 10

仔细思考，奶牛数量上的限制，同时也限制了什么？

是的，因为每一个小组至少得有一头奶牛吧，小组的数量同时也被限制了。

那我们就可以依据小组的数量来处理答案。

假设我们要求某个品种的奶牛分为 v 组。我们找到满足奶牛被分成了 v 组的最大的交流距离，记这个距离为 g_v（用二分）。

我们发现，随着 v 的不断增大，g_v 是不断减小的（理解为越分越细），而在 [g_{v+1}+1,g_v] 之间的距离都能用 v 组分配。

我们用一个前缀和，是不是就可以解决每个距离的答案了？时间复杂度 \Theta(N\log_2N)，带一个 10 （取决于每组数量）的常数。

解决了两个部分分，有没有发现，问题是不是已经解决了？

如果将每个品种奶牛数量分开处理，\le\sqrt N 的用 Subtask 2 方法，反之用 Subtask 1 方法。

我们发现，因为每个品种数量 \le\sqrt N，每种奶牛的数量得到了限制，而我们只需要 \Theta(N\sqrt N \log_2N) 的复杂度来处理第一部分。

而对于 >\sqrt N 的品种，这些品种的个数不会超过 \sqrt N，我们也可以在 \Theta(N\sqrt N\ln N) 的复杂度内处理第二部分。

综上，我们可以在 \Theta(N\sqrt N\log_2 N) 的时间复杂度内处理这个问题。

完结撒花(●'◡'●)！

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,Z=300;
int n,a[N],c[N],e[N],t,o[Z],k,m[N],pos,s,ed[N],to[N],ct[N],sp[N];
int find(int v,int id)//找到最大交流距离g[v]
{
    int l=0,r=sp[v-1],d,x,i,ls,g,ans;//递减的答案，缩小二分范围
    //l可以为0，有些品种的分组有上限，挨太近了
    while(l<=r)
    {
        d=l+r>>1;
        x=to[id],ls=-1e9,g=0;
        for(i=1;i<=c[id];++i)//好比暴力部分，超了范围就开新组
        {
            if(x-ls>d)
              ++g,ls=x;//更新左端点
            x=ed[x];//同种的下一只奶牛
        }
        if(g>=v)
          ans=d,l=d+1;
        else
          r=d-1;
    }
    return ans;
}
void init(int id)//初始化e数组
{
    int i;
    t=n+1;
    for(i=n;i;--i)
    {
        e[i]=t;
        if(a[i]==o[id])
          t=i;
    }
    return ;
}
int main()
{
    int i,j;
    scanf("%d",&n),sp[0]=n;
    for(i=1;i<=n;++i)
      scanf("%d",a+i),++c[a[i]];//统计每种奶牛数量
    for(i=1;i<=n;++i)
    {
        if(c[i]>Z)//分类
          ++k,o[k]=i;
        to[i]=n+1;
    }
    for(j=1;j<=k;++j)
    {
        init(j);//初始化
        for(i=1;i<=n;++i)
        {
            pos=t,s=0;
            while(pos<=n)
            {
                ++s;//开新组
                if(pos+i+1>n)
                  break;
                pos=e[pos+i];//i个i个跳跃
            }
            m[i]=m[i]+s;//统计第一部分答案
        }
    }
    for(i=n;i;--i)
      ed[i]=to[a[i]],to[a[i]]=i;//找到同种的下一只奶牛
    for(i=1;i<=n;++i)
    {
        if(c[i]>Z)
          continue;
        for(j=1;j<=c[i];++j)
          ++ct[sp[j]=find(j,i)];//前缀和统计第二部分答案
    }
    s=0;
    for(i=n;i;--i)
       s=s+ct[i],m[i]=m[i]+s;//前缀和转答案
    for(i=1;i<=n;++i)
      printf("%d\n",m[i]);
    return 0;
}