NOIP 2006 T1 明明的随机数

这道题放进了排序算法作业里，那当然要手写排序（用sort就没意思了）

1. 简化题意：对一个序列进行去重和升序排序；
2. 看数据范围（这点真的很重要），N≤100,a[i]≤1000；
3. 思考做法及优化，本题考虑到去重操作，数据范围又不大，可用桶排，较为方便。楼下的循环去重有点麻烦，桶排本身就能去重

思考：排序和去重怎么做？

1. 先讲去重吧，开一个桶数组 t ，每次都把出现过的数存起来（t[1]>0就表示1出现过），最后把已出现过的数都输出就不会重复了，遇到没出现的数，计数器+1
2. 鱿鱼下标就是我们输出的答案，所以最后输出时，for循环遍历所有可能的答案，一旦发现这个数出现过就输出 i ，i 刚好就是从小到大升序的，所以这个问题就解决了

还能再优化吗？

• 我们都知道桶排的空间大，那么结合上面的思考过程，你能想到怎么优化吗？ 我们发现因为桶是去重用的，所以只考虑这个数在不在，这就不难想到bool类型，用 1 表示这个数已在，0 表示这个数不在（bool代替int，空间就节省了一点点）
• 那么我们又想到每次这个数没出现过再标记，毕竟已经有了还标记没什么用

于是，我们得到以下代码：

#include<bits/stdc++.h>
#define For(i,x,y) for(int i=x;i<=y;i++)
#define Dor(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const int N=105;
int n,tot,maxx;
bool t[N];     //bool类型的桶
int main(){
	//freopen("random.in","r",stdin);
    //freopen("random.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    For(i,1,n){
    	int x;
    	cin>>x;
    	if(!t[x]){    //没遇到过再标记
    		t[x]++;
    		tot++;
    		maxx=max(maxx,x);    //记录出现过的最大答案
		}
	}
	cout<<tot<<'\n';
	For(i,1,maxx)
		if(t[i]) cout<<i<<" ";
	return 0;
}

桶排做法就结束了

最后来提供一种十分方便快捷的做法，不是排序算法哦，相信熟悉 STL 的的人都知道，STL里有一个容器 set ，将数存进去时，它会自动排序和去重，和这道题的要求可以说是100%匹配了，学过的人应该想起来了，没学过的可以去百度以下，我也简略说些跟做这道题目有关的一些知识吧

定义：set<类型> 变量名

存入：变量名.insert(数)

循环遍历（要用迭代器）：

for(auto it=s.begin();it!=s.end();it++)

没学过的可以去了解了解，还算比较实用的，完结！ 终于写完了

这道题需要统计和去重，数据大小<1000,10000时最好的方法是桶排，但是这道题最好练一练循环去重

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a[1010]={0},x,s=0,b[1020];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	for(int i=2;i<=n;i++)
	{
		if(a[i]==a[i-1])
			a[i-1]=0;
	}
	for(int i=1;i<=n;i++)
		if(a[i]!=0)
			s++;
	cout<<s<<endl;

	for(int i=1;i<=1000;i++)
		if(a[i]>0)cout<<a[i]<<' ';
	return 0;
}