BSOJ 1562 【堆练习】丑数3576
2024-09-01 20:56:02
Description
丑数是指素因子都在集合{2,3,5,7}内的整数,第一个丑数是1。
现在输入n(n<=4000),输出第n个丑数。
Input
输入文件仅一行为一个整数n。
Output
输出文件仅一行为一个整数,表示第n个丑数。
Sample Input
5
Sample Output
5
这道题窝先打的STL优先队列 然后全WA。。。。
看了前辈的打表程序 对拍了一下 发现很有问题(废话
后来发现问题出在 丑数集合中不能有重复数字
即 一个相同的数可能被视作多个数
于是乎就短暂的考虑了桶。。。。
当开始试验的时候憨憨癌发作 以为数组只用开4000就OK
后来发现事情没那么简单。。。。。
这个桶应该开到第4000个丑数的值那么大
前辈的打表程序发现是2亿多。。。。。。
(MLE的芳香!
于是飞快放弃了。。。。
最后选用的是C++自带的超强的set函数
先上网自学了一波 知道了set函数具有去重+排序的美妙功能
非常符合这道题的要求啊!
于是自学set过后A了这道水题。。。。。。
果然还是窝太菜了QAQ
set效率很高的 不愧是C++
然后就是0msAC代码:
#include <iostream>
#include <set>
#define maxn 1005
using namespace std;
set <int> a;
int main()
{
a.insert(1);
//先插入堆顶操作元素
int n;
cin>>n;
for(int i=2;i<=n;i++)
//因为初始化堆顶视为一次操作 所以从i=2开始
{
int num=*a.begin();
//先定义一个变量储存当前堆顶
//其实和指针没关系的。。。。
a.insert(num*2);
//分别插入操作数 set会自行排序维护根堆
a.insert(num*3);
a.insert(num*5);
a.insert(num*7);
a.erase(a.begin());
//再将堆顶弹出
}
cout<<*a.begin()<<endl;
//最后的堆顶就是答案啦~~~
return 0;
}
有什么疑问可以问窝 但是窝很菜的。。。
CSP普及才Au宁敢问吗
2020年2月9日10:19更新
在听了did讲课过后 窝知道了这道题其实可以不用set 而且没必要
毕竟这就是一道堆练习嘛
窝再梳理了一下我的心路历程 发现实际上窝离正常确方法就差那么一丢丢
这道题的确要考虑到去重
但没有必要用set去重 因为正如did所说的一样:
“宁现在用了set,以后不能用set的时候宁怎么办?”
所以可以直接在堆的代码里加入少量的盐去重算法以达到同样效果
代码:
#include <iostream>
#include <queue>
#define maxn 1005
using namespace std;
priority_queue <int,vector<int>,greater<int> > a;
//定义一个小根堆
//这里使用的食材(bushi)工具是STL
//各位大佬可以自己手写堆 勿喷蒟蒻
int main()
{
a.push(1);
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
int num=a.top();
//拿出堆顶元素 即操作数
a.push(num*2);a.push(num*3);
//放入其他丑数
a.push(num*5);a.push(num*7);
while(a.top()==num) a.pop();
//去重 只要相同就pop
}
cout<<a.top()<<endl;
//最后的堆顶就是第n个丑数啦~~~
return 0;
}
提交过后性能分析
Time | Memory | Length | |
---|---|---|---|
堆 | 0ms | 1863KB | 0.39KB |
set | 0ms | 1997KB | 0.34KB |
综上分析 堆更优
堆的好处:易懂 易想 耗时较少
set的好处:好写 方便 码量较少
求点赞QAQ不容易啊
常见疑问一:
OI上可以用set吗?
回答:
应该可以 但我没用过(
常见疑问二:
你BB太多 可以举报吗?
回答:
QAQ!!!不看就行啦!!!
最新文章
- nodejs events模块
- iOS10 UI设计基础教程
- bzoj 3389
- Virtual Memory PAGE TABLE STRUCTURE
- HashMap Hashtable ArrayList HashSet
- BestCoder Round #49
- Problem B: Excuses, Excuses!
- 使用JavaScriptSerializer进行序列化日期类型应该注意的问题
- 工作经常使用的SQL整理
- LeetCode OJ 45. Jump Game II
- 移动设备真机调试本地程序的Node.js【无需连wifi】
- python/进程线程的总结
- 敏捷测试(5)--基于story的敏捷基础知识
- Python3 在操作excel时报PermissionError: [Errno 13] Permission denied: &#39;D:/workstation/yhdx_auto/config/case.xls&#39;错误
- Android之数据存储之SharedPreferences
- laravel5.5 excel的安装和使用
- 【rabbitmq】rabbitmq概念解析--消息确认--示例程序
- MVC下载文档
- DEDEcms和帝国cms的几点比较
- delphi 搭建安卓开发环境
热门文章
- Linux下安装MySQL及远程连接MySQL
- A - A Flipping Game
- HDU-6874 Decision 倍增 (2020 HDU多校 D7 D)
- 【bzoj 2163】复杂的大门(算法效率--拆点+贪心)
- hdu5135 Little Zu Chongzhi's Triangles
- Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree (dfs计数,树)
- Codeforces Round #550 (Div. 3) E. Median String (思维,模拟)
- NCD 2019 H. Mr. Hamra and his quantum particles
- Ubuntu中Unable to acquire the dpkg frontend lock (/var/lib/dpkg/lock-frontend)问题的解决
- 排序算法 以及HKU的一些数据结构 相关题目 以及 K叉树,二叉树 排列