首页 > 代码库 > [usaco]丑数
[usaco]丑数
思考
首先产生的思路是，用小根堆的最小元素(top)来与 k个数 相乘，之后把结果再扔进小根堆，每次操作得到的即是第k小。 不过要注意一下判重。但是非常悲剧的是 在遇到极限数据的时候TLE了。在思索无果的情况下，偷偷去看了发题解。发现题目的解法还是比较巧妙的。
#include <queue>#include <cstdio>#include <iostream>#define LL long longusing namespace std;LL num[105],ans[100005],cnt;struct node{ LL x; bool operator < (const node A)const{ return x>A.x; } node(LL x){ this->x=x; }};priority_queue<node>s;int main(){ LL k,n,i; scanf("%lld%lld",&k,&n); for(register int i=1;i<=k;i++){ scanf("%lld",&num[i]); } s.push(node(1)); while(cnt<=n){ LL x = s.top().x; s.pop(); if(ans[cnt]<x){ ans[++cnt]=x; for(register int i=1;i<=k;i++) s.push(node(num[i]*x)); } } printf("%lld",ans[n+1]);}
题解的思路是什么呢？ f[i]表示第i小 那么f[i]一定大于f[i-1] 我们要做的是 f[i]大于f[i-1] 并尽量的小（读者:这不是废话吗？）
其次 f[i]一定是这k个数中的某个数 乘 f[i-1]或者f[i-2]或者f[i-3]....得来的，那么思路就出来了。 但是这三层循环还是有可能TLE。所以要进一步优化.
很容易发现满足条件的丑数x*a[j]>f[i-1]，一定满足条件，x*a[j]>f[i-2];于是我们就可以从满足x*a[j]>f[i-2]的丑数x的位置往后枚举，找到满足条件x*a[j]>f[i-1]的丑数。
然后和min比较。
#include <cstdio>#include <iostream>typedef unsigned long long ll;using namespace std;const int maxn=100011;ll Num[123],f[maxn],jl[maxn];ll n,MIN,k;int main(){ scanf("%lld%lld",&k,&n); for(int i=1;i<=k;i++) scanf("%lld",&Num[i]); f[0]=1; for(int i=1;i<=n;i++){ MIN=3e9; for(int j=1;j<=k;j++){ //为什么要jl[j]++ 因为如果不加的话 到f[i+1] f[jk[j]]*Num[j] 一定也是<=f[i] //其次 s[j]存的是a[j]至少与第几小丑数相乘才能得到一个比f[i-1]大的丑数 while(Num[j]*f[jl[j]]<=f[i-1]) jl[j]++; MIN = min(MIN,Num[j]*f[jl[j]]); } f[i] = MIN; } printf("%lld",f[n]);}
[usaco]丑数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。