vlambda博客
学习文章列表

今年还剩184天可以学习 P5660 P1059 桶排序

今年还剩184天可以学习 P5660 P1059 桶排序



P1059题目描述

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

输入格式

输入有两行,第 1 行为 1 正整数,表示所生成的随机数的个数n,第行有n个用空格隔开的正整数,为所产生的随机数。

输出格式

输出也是两行,第行为个正整数,表示不相同的随机数的个数。

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

输入输出样例

输入

10
20 40 32 67 40 20 89 300 400 15

输出

8
15 20 32 40 67 89 300 400

说明/提示

NOIP 2006 普及组 第一题

解答

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。


今年还剩184天可以学习 P5660 P1059 桶排序

今年还剩184天可以学习 P5660 P1059 桶排序


今年还剩184天可以学习 P5660 P1059 桶排序


我们可以使用桶排序的思想,因为数据范围很小且都是正整数

#include<iostream>using namespace std;int main(){ int n,x; cin>>n; int sum(0),bus[1002]={0}; for(int i=1;i<=n;i++){ cin>>x; if(bus[x]) //如果这个数已经出现过了,那么跳过 continue; bus[x]++; //如果没有出现,把数据放在桶里,并让总数居++ sum++; } cout<<sum<<endl; for(int i=1;i<=1000;i++) if(bus[i]) cout<<i<<' '; cout<<endl; return 0;}



P5660题目描述

小 K 同学向小 P 同学发送了一个长度为 8 的 01 字符串来玩数字游戏,小 P 同学想要知道字符串中究竟有多少个 1。

注意:01 字符串为每一个字符是 0 或者 1 的字符串,如“101”(不含双引号)为一个长度为 3 的 01 字符串。

输入格式

输入文件只有一行,一个长度为 8 的 01 字符串 s。

输出格式

输出文件只有一行,包含一个整数,即 01 字符串中字符 1 的个数。

输入输出样例

输入 

00010100

输出

2

输入

11111111

输出 

8

解答

#include<cstdio>using namespace std;int main(){ char x; int ans=0; for(int i=1;i<=8;i++) { scanf("%c",&x); if(x=='1') ans++; } printf("%d\n",ans); return 0;}



今年还剩184天可以学习 P5660 P1059 桶排序

 
   
   
 
ADay日历
靳晓昀、日历、激励、编程、教育、读书、思维、写作、工商管理
87篇原创内容
Official Account

喜欢这篇文章就点这里