随笔-141  评论-9  文章-3  trackbacks-0

看了官方题解才略懂....囧..

我们在数组hum中计算出前n个丑数。为了实现起来更简单,我们把1也作为一个丑数,算法也要因此略微调整一下。
当我们已知前k个丑数,想得到第k+1个,我们可以这样做:


对于每个质数p 寻找最小的丑数h 使得 h * p 比上一个丑数大

取我们找到的 h * p 中最小的一个:它就是下一个丑数为了使搜索更快,我们可以为每个质数维护一个索引“pindex”表示每个质数已经乘到了哪个丑数,每次都从那里开始,而不是再从头再来。


/*
ID: lorelei3
TASK: humble
LANG: C++
*/


#include 
<fstream>
#include 
<iostream>

using namespace std;

const int MAX = 100000;
const int INF = 0x7FFFFFFF;

int prim[MAX], pindex[MAX];
long hum[MAX];

int K,N,n;

int main(){
    
int i,min,minp;
    ifstream fin(
"humble.in");
    ofstream fout(
"humble.out");

    fin
>>K>>N;

    
for(i=0; i<K; ++i)
        fin
>>prim[i];

    hum[n
++]=1;

    
while(n<N+1){
        min 
= INF; minp=-1;
        
for(i=0; i<K; ++i){
            
while((double)prim[i]*hum[pindex[i]] <= hum[n-1])
                pindex[i]
++;

            
if((double)prim[i]*hum[pindex[i]] < min){
                min 
= prim[i]*hum[pindex[i]];
                minp 
= i;
            }


        }

        hum[n
++= min;
        pindex[minp]
++;
    }


    fout
<<hum[N]<<endl;

    
return 0;
}


posted on 2010-12-15 11:23 小阮 阅读(451) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理