自动搬运

查看原文

来自洛谷，原作者为

	WindowsWKP 互关！||100粉随便问5个问题||主页https://www.luogu.com.cn/paste/ivzwecet|@syd190214还号

搬运于2025-08-24 22:57:10，当前版本为作者最后更新于2024-04-20 08:00:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Update On 4.25：修改为全角符号。

Update On 5.5：代码全部修改为 scanf 和 printf 。（避免剪枝部分歧义）

Update On 7.28：“剪枝”板块改为“优化”板块。

分析

这道题目最基础的枚举思路是：

1. 用桶 $f$ 存下每一种邮票出现的数量。

2. 从 $1$ 到 $n$ 枚举 $k$。

3. 从 $1$ 到 $n$ 判断 ${f}_{i}$ 共有几张可用的邮票。

4. 合成答案，输出结果。

但由于 ${a}_{i}$ 太大，无法存下太大的桶，所以一个简单的处理方式就是离散化，代码 $60$ 分。

#include<bits/stdc++.h>
using namespace std;
int a[300010],n,k,x,y,f[300010],ans;
int main(){
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++){
        if (a[i]!=y)
            x++,y=a[i];
        a[i]=x;
    }
    for (int i=1;i<=n;i++)
        f[a[i]]++;
    for (k=1;k<=n;k++){
        ans=0;
        for (int i=1;i<=n;i++)
            if (f[i]>=k)
                ans+=f[i]-f[i]%k;
        cout<<ans<<" ";
    }
    return 0;
}

优化

这种代码需要排序，又有大规模枚举，必须要优化。

1. 使用 printf 代替 cout ，代码 $60$ 分。

2. 将 $ans$ 改为数组，如果 ${ans}_{k-1}$ 已经是 $0$ 了，就没有继续枚举的必要了。虽然还是 $60$ 分，但子任务 $7,8,9,10$ 开始出现很多通过的点了。

3. 边离散化边装桶，代码还是 $60$ 分，但仍有较小提升，且更为简洁。

4. 判断 ${ans}_{k}$ 时，只判断 $1$ 到 $x$，因为装了东西的桶只有 $x$ 个。代码 $90$ 分，只剩下 $2$ 个点。

5. 对桶进行排序，并在判断 ${ans}_{k}$ 时，如果发现桶已经无法取出邮票了，就停止判断。代码 $100$ 分，且有极大余量。

代码

#include<bits/stdc++.h>
using namespace std;
int a[300010],n,k,x,y,f[300010],ans[300010]={1};
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for (int i=1;i<=n;i++){
        if (a[i]!=y)
            x++,y=a[i];
        a[i]=x;
        f[a[i]]++;
    }
    sort(f+1,f+x+1);
    for (k=1;k<=n;k++){
        ans[k]=0;
        if (ans[k-1]==0)
            break;
        for (int i=x;i>=1;i--){
            if (f[i]>=k)
                ans[k]+=f[i]-f[i]%k;
            else
                break;
        }
        printf("%d ",ans[k]);
    }
    for (k=k;k<=n;k++)
        printf("0 ");
    return 0;
}