NOIP 2006 明明的随机数

淩亂°似流年 2022-05-16 01:05 203阅读 0赞

题目描述

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

输入

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

输出

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

分析：用unique函数去重，unique函数是删除所有相邻的重复元素（只留下一个），这里的删除并不是真正意义上的删除，只是将它放在了末尾。因为unique函数只能去掉相邻的重复元素，为了使相同的都被去掉，所以先给数组排序，再用unique函数去重，函数的返回值是一个迭代器，**它指向的是去重后容器中第一个重复的元素的地址(也就是不重复序列的最后一个元素的下一个元素的地址)**。然后再减去首地址，即可得到该位置的下标。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    const int maxn =1e2+7;
    int a[maxn];
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    int main()
    {
        int n=read();
        fup(i,0,n) a[i]=read();
        sort(a,a+n);
        n=unique(a,a+n)-a;//得到去重后容器中不重复序列的最后一个元素的下一个元素的下标
        printf("%d\n",n);
        fup(i,0,n){
            if(i==0) printf("%d",a[i]);
            else printf(" %d",a[i]);
        }
        printf("\n");
        return 0;
    }