自动搬运

查看原文

来自洛谷，原作者为

	南城忆潇湘 今天又是摸鱼的一天

搬运于2025-08-24 22:05:41，当前版本为作者最后更新于2018-11-04 08:26:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在这里提供一个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;
}