题解 P4960 【血小板与凝血因子】
ouuan
2018-11-23 16:49:38
还是补充一下官方题解中的sort解法（wjyyy嫌我代码太丑没发上来...）
选择容器一，答案为数字的种类数；选择容器二，答案为每种数字个数的最大值。
所以，只要分别求出种类数和每种数字的个数即可。有多种实现方式，排序后扫一遍是其中一种，具体实现可以看代码。
至于方案输出，选择容器一时每个容器放同一个数字，选择容器二时将每种数字的每一个依次放入不同的容器中（这种数字有 $k$ 个就放在前 $k$ 个容器内）。具体实现可以看代码，其中 $plan[i][0]$ 是容器 $i$ 中元素的个数。
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[1010],type,maxx,plan[1010][1010];
int main()
{
int i,j,temp=0;
cin>>n;
for (i=0;i<n;++i)
{
cin>>a[i];
}
sort(a,a+n);
for (i=0;i<n;++i)
{
if (i>0&&a[i]==a[i-1])
{
++temp; //temp表示当前数字的个数
}
else
{
++type; //type表示当前数字是第几种
maxx=max(temp,maxx);
temp=1;
}
}
maxx=max(temp,maxx);
if (type>maxx)
{
type=0;
for (i=0;i<n;++i)
{
if (i>0&&a[i]==a[i-1])
{
++temp;
plan[temp][++plan[temp][0]]=a[i];
}
else
{
++type;
temp=1;
plan[1][++plan[1][0]]=a[i];
}
}
cout<<maxx<<" 2";
for (i=1;i<=maxx;++i)
{
cout<<endl<<plan[i][0];
for (j=1;j<=plan[i][0];++j)
{
cout<<' '<<plan[i][j];
}
}
}
else
{
type=0;
for (i=0;i<n;++i)
{
if (i>0&&a[i]==a[i-1])
{
plan[type][++plan[type][0]]=a[i];
}
else
{
++type;
plan[type][++plan[type][0]]=a[i];
}
}
cout<<type<<" 1";
for (i=1;i<=type;++i)
{
cout<<endl<<plan[i][0];
for (j=1;j<=plan[i][0];++j)
{
cout<<' '<<plan[i][j];
}
}
}
return 0;
}
```