题解 P4960 【血小板与凝血因子】

2018-11-04 07:53:36


大家有发现赛后提交这个题的评测信息彩蛋吗

因为给出了两种容器,而且容器只能统一使用一种,因此一种比较暴力的方式是枚举这两种哪种更优。

实际上我们可以先对$a_i$排序,然后看出现了多少种不同的元素,元素的种类数是只使用容器$1$的答案,同种元素出现次数的最大值是容器$2$的答案。

比较上述两者答案,选择较小的。对容器$1$而言,答案就是每行把同种元素分为一组;对容器$2$而言,假设某种元素出现了$k$次,那么它出现且仅出现在第$1\sim k$组中。这样输出每组的元素数及元素即可,同时因为良心的spj writer可以不按顺序输出。

如果迭代器使用熟练的话,可以直接在std::map中统计答案并输出。

这道题主要考查了对数据的排序。在$n\le 1,000$的数据中,您可以使用任何可以想到的时间复杂度在O(n²logn)以内的排序方法来对$a_i$进行排序。

您甚至可以方便地使用std::sortstd::map来帮您减少代码复杂度,从而在这场ACM赛制的比赛中风生水起。

$\text{ctr}$相信,这道可爱又良心的题目,会让您的比赛之旅有一个好的1A开始,为您的AK之路提供有力的帮助。

Code:

#include<cstdio>
#include<map>
using std::map;
map<int,int> m;
int a[1010];
int ans[1010][1010];
int main()
{
    int n,u;
    scanf("%d",&n);
    int mx=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&u);
        m[u]++;
        mx=mx>m[u]?mx:m[u];
    }
    ans[0][0]=mx<m.size()?mx:m.size();
    printf("%d ",ans[0][0]);
    if(mx<m.size())
    {
        printf("%d\n",2);
        for(map<int,int>::iterator it=m.begin();it!=m.end();++it)
        {
            int num=it->second;
            for(int i=1;i<=num;++i)
                ans[i][++ans[i][0]]=it->first;
        }
        for(int i=1;i<=ans[0][0];++i)
        {
            for(int j=0;j<=ans[i][0];++j)
                printf("%d ",ans[i][j]);
            puts("");
        }
    }
    else
    {
        printf("%d\n",1);
        for(map<int,int>::iterator it=m.begin();it!=m.end();++it)
        {
            int num=it->second;
            printf("%d ",num);
            for(int i=1;i<=num;++i)
                printf("%d ",it->first);
            puts("");
        }
    }
    return 0;
}