华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1519|回复: 7
打印 上一主题 下一主题

P1059 明明的随机数

[复制链接]

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
跳转到指定楼层
楼主
发表于 2018-4-21 16:19:31 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
题目描述
明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入输出格式
输入格式:
输入有2行,第1行为1个正整数,表示所生成的随机数的个数N

第2行有N个用空格隔开的正整数,为所产生的随机数。

输出格式:
输出也是2行,第1行为1个正整数M,表示不相同的随机数的个数。

第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

输入输出样例
输入样例#1:
10
20 40 32 67 40 20 89 300 400 15
输出样例#1:
8
15 20 32 40 67 89 300 400
说明
NOIP 2006 普及组 第一题
回复

使用道具 举报

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
沙发
 楼主| 发表于 2018-4-21 16:28:40 | 只看该作者
第一种做法,因为数字的范围不大,1..1000,所以考虑使用桶排序,用b[x]记录x是否出现,最后按顺序输出x就行。
  1. #include<iostream>
  2. using namespace std;
  3. const int mn=1010;
  4. bool  b[mn];
  5. int N,M,i,x;
  6. int main()
  7. {
  8.     for (i=1; i<=mn-1; i++) b[i]=0; ///重要变量初值检查
  9.     cin>>N;
  10.     for (i=1; i<=N; i++)
  11.     {
  12.         cin>>x;    ///读得数据并置位
  13.         b[x]=1;
  14.     }
  15.     for (i=1; i<=mn-1; i++) M+=b[i]; ///累加求和
  16.     cout<<M<<endl;
  17.     for (i=1; i<=mn-1; i++) if (b[i]) cout<<i<<' '; ///判断并输出
  18.     return 0;
  19. }
复制代码
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
板凳
 楼主| 发表于 2018-4-21 16:45:36 | 只看该作者
第二种做法,先排序,这样相同的数就在一起了,然后导到另外一个数组,统计个数,输出。这适合数据范围比较大,不好进行桶排序的
  1. #include<iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. const int mn=1010;
  5. int a[mn],b[mn];
  6. int N,M,i,j;
  7. int main()
  8. {

  9.     cin>>N;
  10.     for (i=1; i<=N; i++) cin>>a[i];
  11.     sort(a+1,a+N+1,less<int>()); //调用系统sort,注意参数形式
  12.     ///for (i=1; i<=N; i++) cout<<a[i]<<' ';///输出检查
  13.     b[1]=a[1];
  14.     for (i=2,j=1;i<=N;i++)
  15.     {
  16.         if (a[i]>b[j]) {j++;b[j]=a[i];} ///大于的话就加在后面,等于不管了
  17.     }
  18.     cout<<j<<endl;
  19.     for (i=1;i<=j;i++) cout<<b[i]<<' ';
  20.     return 0;
  21. }
复制代码
回复 支持 反对

使用道具 举报

9

主题

89

帖子

292

积分

华一学生

积分
292
地板
发表于 2018-4-22 20:56:46 | 只看该作者
  1. #include<iostream>
  2. using namespace std;
  3. const int mx=1100;
  4. int a;
  5. bool b[mx];
  6. int i,n,maxn;
  7. int main()
  8. {
  9.     cin>>n;
  10.     for (i=1;i<=n;i++)
  11.     {
  12.         int a;
  13.         cin>>a;
  14.         b[a]=true;
  15.     }
  16.     for (i=1;i<=1000;i++)
  17.     {
  18.         if (b[i]) maxn++;
  19.     }
  20.     cout<<maxn<<endl;
  21.     for (i=1;i<=1000;i++)
  22.     {
  23.         if (b[i]) cout<<i<<" ";
  24.     }
  25.     return 0;
  26. }
复制代码
回复 支持 反对

使用道具 举报

2

主题

105

帖子

306

积分

中级会员

Rank: 3Rank: 3

积分
306
5#
发表于 2018-5-14 14:06:43 | 只看该作者
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <algorithm>
  7. using namespace std;
  8. int main()
  9. {
  10.         int a[10000],n,i,g,r;
  11.         scanf("%d",&n);
  12.         for(i=1; i<=n; i++)
  13.         {
  14.                 scanf("%d",&a[i]);
  15.         }
  16.         sort(a+1,a+n+1);
  17.         r=n;
  18.         for(i=1; i<=n; i++)
  19.         {
  20.                 if(a[i]!=g)
  21.                 {
  22.                         g=a[i];

  23.                 }
  24.                 else
  25.                         r--;
  26.         }
  27.         printf("%d\n",r);
  28.         for(i=1; i<=n; i++)
  29.         {
  30.                 if(a[i]!=g)
  31.                 {
  32.                         printf("%d ",a[i]);
  33.                         g=a[i];
  34.                 }
  35.         }
  36.         return 0;
  37. }
复制代码
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5420

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5420
6#
 楼主| 发表于 2018-5-14 16:00:44 | 只看该作者
我总觉得很奇怪,为什么你们的程序都比我的长很多呢?我也没有刻意的把几句话放在一起呀
回复 支持 反对

使用道具 举报

50

主题

215

帖子

619

积分

高级会员

Rank: 4

积分
619
7#
发表于 2018-7-18 14:49:41 | 只看该作者
  1. #include<iostream>
  2. using namespace std;
  3. int n,a[1010],ans,b;
  4. int i,j;
  5. int main()
  6. {
  7.     cin>>n;
  8.     for(i=1;i<=n;i++)
  9.     {
  10.         cin>>b;
  11.         a[b]=1;
  12.     }
  13.     for(i=1;i<=1000;i++)if(a[i]==1)ans++;
  14.     cout<<ans<<endl;
  15.     for(i=1;i<=1000;i++)if(a[i]==1)cout<<i<<" ";
  16.     return 0;
  17. }
复制代码
回复 支持 反对

使用道具 举报

9

主题

158

帖子

470

积分

华一学生

积分
470
QQ
8#
发表于 2018-8-25 16:17:35 | 只看该作者
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. int n,a[101],l=1;
  5. int main()
  6. {
  7.     cin>>n;
  8.     for(int i=1;i<=n;i++)cin>>a[i];
  9.     sort(a+1,a+n+1);
  10.     unique(a+1,a+n+1);
  11.     while(l<n&&a[l]<a[l+1])l++;
  12.     cout<<l<<endl;
  13.     for(int i=1;i<=l;i++)cout<<a[i]<<' ';
  14.     return 0;
  15. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-11-1 22:27 , Processed in 0.133771 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表