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

· · 题解

在这里提供一个map的做法：
做一个小简介：
map(映射,mapping的缩写)，分为键值和数据值。在头文件map中。它内部是一颗红黑树，按照键值大小排好序（也就是说，果你要按照你自己的顺序排序的话，就要重载运算符）。
它可以直接用[]运算符调用，所以它又称为关联数组（把它当做普通的数组使用就行）。调用的时间复杂度为O(log_2N),N为储存元素的多少。
那我们要遍历这个映射的话应该怎么办呢？没关系，STL库中有一个iterator（迭代器）的东东。在这道题目中，我们就可以使用它来（快速）解题。
调用iterator的方法：

map <键值的类型,数据值的类型> :: iterator 迭代器名称

看，是不是很方便。假如我们定义了一个it迭代器。那么，它可以支持的操作有（只列举出在这题需要的内容）。

1.自加/自减。也就是 ++/-- ,例如：it++/it--。
注意：这里自加/自减如果超出map的范围，会运行时错误。自加表示访问后一个值，自减表示访问前一个值。

2.删除当前的值。 erase(it)。注意，如果当前删除it的话，it++或者it--就会越界（因为你现在已经不在map中间了）。所以我们可以再开一个迭代器now,然后it++删除now即可。（下文的代码也是这样写的）。

3.访问it指向（貌似没有一个专业的术语，就说指向吧）的值。由于map中的元素由两种类型组成（其实就是一个pair），所以我们可以有两种方法调用：
1.it->first/second
2.(*it).first/second
first为键值，second为数据值。

下面就可以放代码（水过这道题啦），注意一下，下面的ans1和ans2分别对应第二种、第一种情况

#include<bits/stdc++.h>
#define MAXN 1001
using namespace std;
int a[MAXN];
map<int,int> b;
int main(){
    int n,ans1=0,ans2=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),b[a[i]]++,ans1=max(ans1,b[a[i]]);
    sort(a+1,a+1+n);
    ans2=unique(a+1,a+1+n)-a-1;
    if(ans2<ans1){
        cout<<ans2<<" "<<1<<endl;
        map<int,int>::iterator it=b.begin();
        for(int i=1;i<=ans2;i++){
            cout<<it->second<<" ";
            for(int j=1;j<=it->second;j++)
                printf("%d ",it->first);
            it++;   
            cout<<endl;
        }
    }
    else {
        cout<<ans1<<" "<<2<<endl;
        for(int i=1;i<=ans1;i++){
            map<int,int>::iterator it=b.begin();
            cout<<b.size()<<" ";
            while(it!=b.end()){
                if(b[(*it).first]>0)    cout<<it->first<<" ",b[(*it).first]--; 
                map<int,int>::iterator now=it; it++;
                if(now->second==0)  b.erase(now);   
            }       
            cout<<endl;     
        }
    }
    return 0;
}