wikioi 1246 堆或贪心

本文主要是介绍wikioi 1246 堆或贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对于一给定的素数集合 S = {p1, p2, ..., pK}, 
来考虑那些质因数全部属于S 的数的集合。这个集合包括，p1, p1p2, p1p1, 和 p1p2p3 (还有其它)。这是个对于一个输入的S的丑数集合。
注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找集合中的第N个丑数。longint(signed 32-bit)对于程序是足够的。

第 1 行: 二个被空间分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000. 
第 2 行: K 个被空间分开的整数:集合S的元素

单独的一行，写上对于输入的S的第N个丑数。

4 19
2 3 5 7

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;
}

这篇关于wikioi 1246 堆或贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---