题解 P4960 【血小板与凝血因子】
wjyyy
·
·
题解
大家有发现赛后提交这个题的评测信息彩蛋吗
因为给出了两种容器，而且容器只能统一使用一种，因此一种比较暴力的方式是枚举这两种哪种更优。
实际上我们可以先对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赛制的比赛中风生水起。
## 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;
}
```