NOIP 2006 明明的随机数

洛谷 P1059 明明的随机数

JDOJ 1423: [NOIP2006]明明的随机数 T1

Description

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

Input

输入有2行，第1行为1个正整数，表示所生成的随机数的个数： N 第2行有N个用空格隔开的正整数，为所产生的随机数。

Output

输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

Sample Input

10 20 40 32 67 40 20 89 300 400 15

Sample Output

8 15 20 32 40 67 89 300 400

Source

NOIP2006普及组

题解：

语法基础题：可以练模拟，也可以练STL中的set容器。

代码1，纯模拟做法：

#include<cstdio>//扫两遍，一遍出次数一遍输出
#include<algorithm>
using namespace std;
int n,ans;
int a[110];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[i-1])
            continue;
        else
            ans++;
    }
    printf("%d
",ans);
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[i-1])
            continue;
        else
            printf("%d ",a[i]);
    }
    return 0;
}

前方高能！！

C++党有一种P党永远比不了的东西：STL。

气死人的现实是，当P党还在考场上手写快排的时候，C++的人一个sort();就能过；当P党还在写代码一模拟时，C++党一个set，码长更小，简洁明了，AC通过。

所以我们来学习这个set容器。

set是英文“集合”的意思，所以，set容器本身就是一个集合。

只不过它又有一个新名字：有序集合。

我们简单地记住set容器的两个特性：元素不重复，元素有序。

难道不是正好满足这个题的意思么？

一个稍微有STL基础的人，就可以摸索着用setA掉本题了。

（注：因为STL的容器函数差不多都是一样的，都可以一通百通）

直接上代码：

#include<cstdio>
#include<set>
using namespace std;
int n;
set<int> s;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        s.insert(x);//集合插入函数
    }
    printf("%d
",s.size());//集合大小函数
    while(!s.empty())//集合是否为空
    {
        printf("%d ",*s.begin());//注意这里一定要用*表示取值（begin是迭代器（返回指针））
        s.erase(s.begin());
    }
    return 0;
}