题解：P10355 [PA2024] Znaczki pocztowe

· · 题解

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;
}