题解 P4960 【血小板与凝血因子】
wjyyy
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::sort`、`std::map`来帮您减少代码复杂度，从而在这场ACM赛制的比赛中风生水起。
$\text{ctr}$相信，这道可爱又良心的题目，会让您的比赛之旅有一个好的~~1A~~开始，为您的AK之路提供有力的帮助。
## Code：
```cpp
#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;
}
```