洛谷P2527 [SHOI2001]Panda的烦恼
题目描述
panda是个数学怪人,他非常喜欢研究跟别人相反的事情。最近他正在研究筛法,众所周知,对一个范围内的整数,经过筛法处理以后,剩下的全部都是质数,不过panda对这些不感兴趣,他只对被筛掉的数感兴趣,他觉得在这些被筛掉的数中一定隐藏着重要的宇宙秘密,只是人们还没有发现罢了。
panda还觉得如果只是单纯地从小到大筛的话,还不足够发现其中的奥秘,于是他决定对至多只包含某些质因数的数进行研究(比如说至多只包含质因数2,3的数有2,3,4,6,8,9,……),他需要得到这些数中第k小的数(k是panda认为的宇宙系数),请你编个程序,帮助他找到这个数。
输入输出格式
输入格式:
第1行有2个数n,k,n代表质因数的个数,k代表那个宇宙系数(1<=n<=100,1<=k<=100000)
第2行有n个数,代表这n个质因数。(每个均小于1000,且不相同)
输出格式:
仅1行,即至多只包含这n个质因数的数中第k小的数。(这个数不会超过2000000000)
输入输出样例
2 7
3 5
45
说明
样例说明:前6个分别是3,5,9,15,25,27。
分析:一个想法是维护一个优先队列,每次取最小值和所有素数相乘,结果放进优先队列里直到出现k个元素,这样也可以拿到很高的分数,但是不是最好的,对于可以用优先队列做的题,有一个非常常用的方法就是把优先队列转化为普通队列.such as:noip2016蚯蚓,只要想方设法把一个队列变成单调的队列就好了,那么这道题怎么变呢?
先把所有的质数依次放到队列里,一开始是单调的,我们要用优先队列的方式来维护,当一个质数乘了第i个元素后,它下一个乘的一定是第i+1个元素,而且保证结果是单调的。每个质数乘一下后会得到多个质数,找到最小的那个数,插入队列里,在插入之前要先判一下重.
这个判重有点小技巧,我一开始想着一个bool数组,可是太大了开不下,map似乎也不行,其实这个队列是单调的,我们只需要看队尾元素有没有重复就好了......
优先队列---->“单调队列”,神奇的优化.而这个优化的关键,就是我们要如何让它单调,像优先队列一样操作.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map> using namespace std; const int inf = ; int n,k,prime[],q[],tot,mx;
int cnt[],cc;
map <int,int> flag; int main()
{
scanf("%d%d",&n,&k);
for (int i = ; i <= n; i++)
scanf("%d",&prime[i]);
q[++tot] = ;
for (int i = ; i <= n; i++)
cnt[i] = ;
while (tot != k + )
{
mx = inf;
for (int i = ; i <= n; i++)
{
int t = q[cnt[i]] * prime[i];
if (t < mx)
{
cc = i;
mx = t;
}
}
cnt[cc]++;
if (mx != q[tot])
q[++tot] = mx;
}
printf("%d\n",q[k + ]); return ;
}
最新文章
- HDU - 1875 畅通工程再续
- C++ operator 的一种不会的用法
- top 10 tipis on Logging in Java- Tutorial (翻译)
- 解决asp.net Core Mvc网页汉字乱码问题
- web前端基础篇②
- winform去掉右上角关闭按钮
- 测试web数据库的分布式事务atomikos 的三种数据源 SimpleDataSourceBean,AtomikosDataSourceBean,AtomikosNonXADataSourceBean
- libyuv颜色空间转换开源库
- [转]Form Builder:app_field.clear_dependent_fields和APP_FIELD.set_dependent_field的用法
- 往另外1个ListView中添加当前选中的项目
- 关于OC中的几种代码延迟执行方式
- Apache RewriteCond RewriteRule 入门和Laravel去掉index.php
- beta版本复审
- js的事件流事件机制
- MySQL的log_bin和sql_log_bin 的区别
- cocos 自动内存管理分析
- [转]angular2封装material2对话框组件
- R1题解
- 75.Java异常处理机制-手动抛出异常
- 对 JavaScript 下 namespace 功能的简单分析