随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.1.3 Humble Numbers

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

我们在数组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 小阮 阅读(453) 评论(0)  编辑 收藏 引用 所属分类: USACO

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮