首页 > 代码库 > wikioi 1246 堆或贪心
wikioi 1246 堆或贪心
题目描述 Description
对于一给定的素数集合 S = {p1, p2, ..., pK},
来考虑那些质因数全部属于S 的数的集合。这个集合包括,p1, p1p2, p1p1, 和 p1p2p3 (还有其它)。这是个对于一个输入的S的丑数集合。
注意:我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找集合中的第N个丑数。longint(signed 32-bit)对于程序是足够的。
输入描述 Input Description
第 1 行: 二个被空间分开的整数:K 和 N , 1<= K<=100 , 1<= N<=100,000.
第 2 行: K 个被空间分开的整数:集合S的元素
输出描述 Output Description
单独的一行,写上对于输入的S的第N个丑数。
样例输入 Sample Input
4 19
2 3 5 7
样例输出 Sample Output
27
这题刚开始用小顶堆做,因为是照着笨的思想做的,有人竟然过了。但是我竟然T了,原因是用了优先队列,然后还用了map,所以不T才怪,但是已经不知道哪里能优化了。最后也只能贪心过了。惭愧啊。
贪心AC的代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<set> #include<bitset> #define INF 100007 using namespace std; typedef long long ll; typedef unsigned long long ull; ll a[1000010]; int b[110],vis[105]; int main() { int k,n,i; cin>>k>>n; for(i=1; i<=k; i++) scanf("%d",b+i); sort(b+1,b+k+1); a[0]=1; for(i=1; i<=n+1; i++) { while(1) { ll Min=0x7fffffff; int j,ii; for(j=1; j<=k; j++) if(Min>a[vis[j]]*b[j]) Min=a[vis[j]]*b[j],ii=j; vis[ii]++; if(Min!=a[i-1]) {a[i]=Min;break;} } } cout<<a[n]<<endl; return 0; }
堆超时的代码:可能以后会想到优化再重新交了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<set> #include<bitset> #define INF 100007 using namespace std; typedef long long ll; typedef unsigned long long ull; priority_queue<ll,vector<ll>,greater<ll> >heap; map<ll,int>Map; int main() { int k,n,i,cnt=-1; ll m,a[105],s; scanf("%d%d",&k,&n); for(i=0;i<k;i++) scanf("%lld",a+i); heap.push(1); while(cnt<n) { cnt++; m=heap.top();heap.pop(); for(i=0;i<k;i++) { s=m*a[i]; if(!Map[s]&&s<(1LL<<31LL)) heap.push(s),Map[s]=1; } } printf("%d\n",m); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。